[字符串]最长不重复子串

题目描述：

最长不重复子串(Longest No Repeat String,LNRS)就是从一个字符串中找到一个连续子串，该子串中任何两个字符都不能相同，且该子串的长度是最大的。

分析：

解法一：动态规划

动态规划就是用来解决这种最优化问题，关于字符串的很多有趣的问题如最长公共自序列，最长上升子序列等都可以用动态规划来解，这道题我的第一想法也是动态规划。

动态规划的核心在于寻找最优子结构,对于一个字符，如果他与他前面的最长不重复子串都没有相同的字符，那么他也可以加入这个子串中，构成一个新的子串。即对于字符数组a[],dp[i]表示以a[i]为结尾的最长不重复子串长度，dp[0] = 1,最后取dp中的最大值即可。代码如下：

1 #include <cstdio> 2 #include <cstdlib> 3 #include <string.h> 4 5 using namespace std; 6 char in[10001]; 7 8 int dp[10001]; 9 10 int LNRS_dp(char *in)11 {12int i, j;13int len = strlen(in);14int last = 0;// 上一次最长子串的起始位置15int maxlen,maxindex;16maxlen = maxindex = 0;17 18dp[0] = 1;19for(i = 1; i < len; ++i)20{21 for(j = i-1; j >= last; --j) // 遍历到上一次最长子串起始位置22 {23 if(in[j] == in[i])24 {25 dp[i] = i - j;26 last = j+1; // 更新last_start27 break;28 }else if(j == last) // 无重复29 {30 dp[i] = dp[i-1] + 1;//长度+1 31 }32 }33 if(dp[i] > maxlen)34 {35 maxlen = dp[i];36 }37}38return maxlen;39 }40 41 int main()42 {43freopen("1530.in","r",stdin);44freopen("1530.out","w",stdout);4546while(scanf("%s",in)!=EOF)47{48 printf("%d\n",LNRS_dp(in));49}50return 0;51 }

View Code

显然这个方案是O(n2)的复杂度，且对字符种类没有限制。

解法二：Hash

很多情况下，在描述一个字符串时，都是英文字母组成的字符，因此可能出现的元素是有限的(26个)，因此就有了第二种想法，Hash。

这种想法在于使用一个大小为26的数组visited[]记录每个字符是否出现，然后枚举最长不重复子串的起点。代码如下：

1 void LNRS_hash(char* s) 2 { 3char visited[26]; 4int i, j; 5int maxlen = 0; 6int maxIndex; 7int len = strlen(s); 8 9memset(visited, -1, 26);10for (i = 0; i < len; i++)11{12 visited[s[i] - 'a'] = 1;13 for(j = i+1 ; j < len; j++)14 {15 if(visited[s[j]-'a'] == -1) //该字符没有出现16 {17 visited[s[j]-'a'] = 1;18 if(j - i+1> maxlen)19 {20 maxlen = j - i+1;21 maxIndex = i;//最长不重复子串的起点22 }23 }24 else25 break;26 }27 memset(visited, -1, 26);28}29printf("%d\n", maxlen);30 }

View Code

这也是O(n2)的复杂度。仅适用于字符种类明确的情形。

解法三：动态规划的改进

有了第二种Hash的思想，我们是不是也可以考虑对第一种动态规划的方法进行针对性改造呢？

回顾之前动态规划的解法，枚举每一个以a[i]为结尾的最长不重复子串，将a[i]与之前的子串元素一一比较，判断是否出现过。很显然，在字符种类有限的情况下(如只有字母组成的字符串)，这种判重可以用Hash来实现。代码如下：

1 int LNRS_dp(char *in) 2 { 3int i, j; 4int len = strlen(in); 5int last = 0;// 上一次最长子串的起始位置 6int maxlen; 7char visited[26]; 8memset(visited, -1, sizeof(visited)); 9dp[0] = 1;10visited[in[0]-'a'] = 0;11maxlen = 1; 12for(i = 1; i < len; ++i)13{14 if(visited[in[i]-'a'] == -1 || visited[in[i]-'a']<last)//未访问过，或者是之前访问的 15 {16 dp[i] = dp[i-1] + 1;17 visited[in[i]-'a'] = i; 18 }19 else20 {21dp[i] = i - visited[in[i]-'a'];22last = visited[in[i]-'a']+1;23visited[in[i]-'a'] = i;24 }25 if(dp[i] > maxlen)26 {27 maxlen = dp[i];28 }29}30return maxlen;31 }

View Code

PS：这是一个OJ的题，/problem.php?pid=1530，前两种方法可以过，第三种方法过不了，求大神指导下，第三种方法哪里没有考虑到，多谢！

有网友给出了一个更简洁的解法，思想与解法三是类似的，代码如下：

1 #include <cstdio> 2 #include <cstring> 3 4 int main() 5 { 6char s[10001]; 7while (scanf("%s", s) != EOF) 8{ 9 int p[128];10 for (char c = 'a'; c <= 'z'; ++c)11 {12 p[c] = -1;13 }14 15 int n = strlen(s), right = -1, answer(0);16 for (int i = 0; i < n; ++i)17 {18 if (p[s[i]] > right)19 {20 right = p[s[i]];21 }22 p[s[i]] = i;23 24 if (i - right > answer)25 {26 answer = i - right;27 }28 }29 30 printf("%d\n", answer);31}32 33return 0;34 }

View Code