首页 > 代码库 > 最长不重复子串（转）
最长不重复子串（转）
对于最长不重复子串，某个当前的字符，如果它与前面的最长不重复子串中的字符没有重复，
那么就可以以它为结尾构成新的最长子串；如果有重复，且重复位置在上一个最长子串起始位置之后，
那么就与该起始位置之后的稍短的子串构成新的子串或者单独成一个新子串。
举个例子：例如字符串“abcdeab”，第二个字符a之前的最长不重复子串是“abcde”，
a与最长子串中的字符有重复，但是它与稍短的“bcde”串没有重复，于是它可以与其构成一个新的子串，之前的最长重复子串“abcde”结束；
再看一个例子：字符串“abcb”，跟前面类似，最长串“abc”结束，第二个字符b与稍短的串“c”构成新的串；
这两个例子，可以看出些眉目：当一个最长子串结束时（即遇到重复的字符），新的子串的长度是与第一个重复的字符的下标有关的，
如果该下标在上一个最长子串起始位置之前，则dp[i] = dp[i-1] + 1，即上一个最长子串的起始位置也是当前最长子串的起始位置；
如果该下标在上一个最长子串起始位置之后，则新的子串是从该下标之后开始的。
因为查询每个字母是否重复时，都要“回头”去寻找，受启发于最初的Hash思路，我们可以用hash记录元素是否出现过，
我们当然也可以用hash记录元素出现过的下标，既然这样，在DP方案中，我们何不hash记录重复元素的位置，
这样就不必“回头”了，而时间复杂度必然降为O(N)，只不过需要一个辅助的常数空间visit[256]，典型的空间换时间。
因此，只需要 dp[i] = dp[i-1] + 1 贪心+Hash 即可解决
#include<iostream>#include<memory.h>#include<string>using namespace std;void output(char * arr);int visit[255];int maxlen;int maxindex;/* LNRS dp + hash 优化 */void LNRS_dp_hash(char * arr, int size){ memset(visit, -1, sizeof visit); maxlen = maxindex = 0; //单个首字母比不重复，只需要初始化。 visit[arr[0]] = 0; int curlen = 1; int start = 0; for(int i = 1; i < size; ++i){ if(visit[arr[i]] == -1){// 该字母第一次加入“最串” ++curlen; visit[arr[i]] = i; // 记录字符下标 }else{//字母arr[i] 非第一次访问，则需要判断上一次访问的位置与当前“最串”起始位置的前后。 if(start <= visit[arr[i]]){//形如: abcda 中的 a 一样，需要更新当前“最串”,成为：bcda 。 curlen = i - visit[arr[i]]; last_start = visit[arr[i]] + 1; visit[arr[i]] = i; // 更新最近重复位置 }else{//形如: aba...adeb 中的b，需要将当前b加入“最串”，成为: adeb ++curlen; visit[arr[i]] = i; // 更新最近重复位置 } } if(curlen > maxlen){//记录最长 maxlen = curlen; maxindex = i + 1 - maxlen; } } output(arr);}void output(char * arr){ if(maxlen == 0) { printf("NO LNRS\n"); } printf("The len of LNRS is %d\n",maxlen); int i = maxindex; while(maxlen--) { printf("%c",arr[i++]); } printf("\n");} void main(){ char arr[] = "abcaacdeabacdefg"; /* LNRS dp + hash 优化方案 */ LNRS_dp_hash(arr,strlen(arr));}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。