字符串中最长不重合子串长度-白红宇

例子

"abmadsefadd" 最长长度为5

"avoaid" 最长长度为3

思路

空间换时间hashTable，起始位置设为beg。初始化全局最大值0。开辟字符数组，起初标为0。

访问数组时

如果该字符在hashTable对应的哈希值为1，则计算当前位置到beg的距离，并且把beg赋值为beg+1。如果大于全局最大值，则替换全局最大值

如果该字符在hashTable对应的哈希值为0，则置1

参考代码

#include 
     
      using namespace std;int getMaxLen(const string &s){    int beg = 0;    int span = 0;    int maxspan = 0;    int hashTable[128];    for (int i = 0; i < 128; ++i)        hashTable[i] = 0;    int lens = s.size();    for(int i = 0; i < lens; ++i)    {        int index = s[i];        if (hashTable[index] == 1)        {            span = i - beg;            if (span > maxspan)                maxspan = span;            beg++;        }        else        {            hashTable[s[i]] = 1;        }    }    return maxspan;}int main(){    const string a = "abmadsefadd";    const string a1 = "avoaid";    cout << getMaxLen(a) << endl;    cout << getMaxLen(a1) << endl;}

结果

7
3

本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3822923.html，如需转载请自行联系原作者