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

题目描述：

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

分析：

解法一：动态规划

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

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

#include <cstdio>
#include <cstdlib>
#include <string.h>

using namespace std;
char in[10001];

int dp[10001];

int LNRS_dp(char *in)
{
    int i, j;
    int len = strlen(in);
    int last = 0;     // 上一次最长子串的起始位置
    int maxlen,maxindex;
    maxlen = maxindex = 0;
 
    dp[0] = 1;
    for(i = 1; i < len; ++i)
    {
        for(j = i-1; j >= last; --j) // 遍历到上一次最长子串起始位置
        {
            if(in[j] == in[i])
            {
                dp[i] = i - j;
                last = j+1; // 更新last_start
                break;
            }else if(j == last) // 无重复
            {
                dp[i] = dp[i-1] + 1;//长度+1 
            }
        }
        if(dp[i] > maxlen)
        {
            maxlen = dp[i];
        }
    }
    return maxlen;
}

int main()
{
     freopen("1530.in","r",stdin);
     freopen("1530.out","w",stdout);
     
     while(scanf("%s",in)!=EOF)
     {
          printf("%d
",LNRS_dp(in));
     }
     return 0;
}

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

解法二：Hash

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

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

void LNRS_hash(char*  s)
{
    char visited[26];
    int i, j;
    int maxlen = 0;
    int maxIndex;
    int  len = strlen(s);

    memset(visited, -1, 26);
    for (i = 0; i < len; i++)
    {
        visited[s[i] - 'a'] = 1;
        for(j = i+1 ; j < len; j++)
        {
            if(visited[s[j]-'a'] == -1) //该字符没有出现
            {
                visited[s[j]-'a'] = 1;
                if(j - i+1> maxlen)
                {
                    maxlen = j - i+1;
                    maxIndex = i;//最长不重复子串的起点
                }
            }
            else
                break;
        }
        memset(visited, -1, 26);
    }
    printf("%d
", maxlen);
}

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

解法三：动态规划的改进

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

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

int LNRS_dp(char *in)
{
    int i, j;
    int len = strlen(in);
    int last = 0;     // 上一次最长子串的起始位置
    int maxlen;
     char visited[26];
     memset(visited, -1, sizeof(visited));
    dp[0] = 1;
    visited[in[0]-'a'] = 0;
    maxlen = 1; 
    for(i = 1; i < len; ++i)
    {
        if(visited[in[i]-'a'] == -1 || visited[in[i]-'a']<last)//未访问过，或者是之前访问的 
        {
             dp[i] = dp[i-1] + 1;
             visited[in[i]-'a'] = i; 
        }
        else
        {
              dp[i] = i - visited[in[i]-'a'];
              last = visited[in[i]-'a']+1;
              visited[in[i]-'a'] = i;
        }
        if(dp[i] > maxlen)
        {
            maxlen = dp[i];
        }
    }
    return maxlen;
}

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

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

#include <cstdio>
#include <cstring>
  
int main()
{
    char s[10001];
    while (scanf("%s", s) != EOF)
    {
        int p[128];
        for (char c = 'a'; c <= 'z'; ++c)
        {
            p[c] = -1;
        }
  
        int n = strlen(s), right = -1, answer(0);
        for (int i = 0; i < n; ++i)
        {
            if (p[s[i]] > right)
            {
                right = p[s[i]];
            }
            p[s[i]] = i;
  
            if (i - right > answer)
            {
                answer = i - right;
            }
        }
  
        printf("%d
", answer);
    }
  
    return 0;
}