最长不重复子串（动态规划最长不重复子串+Hash）

布满荆棘的人生 2022-08-03 05:24 206阅读 0赞

题目1530：最长不重复子串

时间限制：1 秒

内存限制：128 兆

特殊判题：否

提交：1138

解决：373

**题目描述：**

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

**输入：**

输入包含多个测试用例，每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串，字符串的长度不大于10000。

**输出：**

对于每组测试用例，输出最大长度的不重复子串长度。

**样例输入：**

absd
    abba
    abdffd

**样例输出：**

4
    2
     4

#include <iostream>
    #include <cstdio>
    #include<vector>
    #include <cstring>
    const int N=10000000;
    using namespace std;
    int myHash[30];
    char vec[N];
    int solve(char *vec,int n)
    {
        int lastpos,global,local;
        lastpos=global=local=0;
        memset(myHash, 0, sizeof(myHash));
        for(int i = 0; i <n; i ++)
        {
             int key = vec[i]-'a';
             myHash[key] ++;
             if(myHash[key] == 2)
             {
                global = max(global, local);
                for(; lastpos < i && vec[lastpos] != vec[i]; lastpos++)
                {
                    myHash[vec[lastpos]-'a']--;
                }
                local = i - lastpos;
                myHash[key]--;
                lastpos++;
             }
             else
             {
                local ++;
             }
        }
        global = max(global, local);
        return global;
    }
    int main()
    {
        int t,n,i,a;
        while(cin>>vec)
        {
           n=strlen(vec);
           cout<<solve(vec,n)<<endl;
        }
    }