首页 > 代码库 > 最长不重复子串
最长不重复子串
用visit数组记录出现过的地方
dp的时候注意一个问题就可以：
abcdacbd来看看如果遇到重复的该怎么处理：
遇到第二个a前都没有问题，第二次遇到a，然后肯定是更新a的位置的dp[4] = 4-0 = 4,
第二次遇到c, 更新c的位置为dp[5] = 5-2 = 3;
然后问题来了，第二次遇到b，从第一个b和第二个b之间已经重复c了，所以只能更新dp[6] = dp[5]+1，所以这里的问题在于，如何标记dp[i]=dp[i-1]+1还是dp[i]=i-visit[a[i]]..............所以这里判断的方法就是，使用一个指针last标记刚刚更新过的地方，比如更新c后，标记last = 5+1(就是第二个c的后一位),然后
if(visit[a[i]] < last)//说明第一个b和第二个b直接有c重复了 dp[i] = dp[i-1]+1;else dp[i] = i - visit[a[i]]; last = i+1;
/* LNRS dp + hash 优化 */void LNRS_dp_hash_impro(char * arr, int size){ memset(visit, -1, sizeof visit); maxlen = maxindex = 0; visit[arr[0]] = 0; int curlen = 1; int last_start = 0; for(int i = 1; i < size; ++i) { if(visit[arr[i]] == -1) { ++curlen; visit[arr[i]] = i; /* 记录字符下标 */ }else { if(last_start <= visit[arr[i]]) { curlen = i - visit[arr[i]]; last_start = visit[arr[i]] + 1; visit[arr[i]] = i; /* 更新最近重复位置 */ }else { ++curlen; visit[arr[i]] = i; /* 更新最近重复位置 */ } } if(curlen > maxlen) { maxlen = curlen; maxindex = i + 1 - maxlen; } } output(arr);}
最长不重复子串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。