首页 > 代码库 > 字符串中最长的不重合字串长度

字符串中最长的不重合字串长度

例子

"abmadsefadd"  最长长度为5

"avoaid"           最长长度为3

 

思路

空间换时间hashTable,标准下其实位置beg。初始化全局最大值0。开辟字符数组,起初标为0。

访问数组时

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

 

参考代码

#include <iostream>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;    for(int i = 0; i < s.size(); ++i)    {        if (hashTable[s[i]] == 1)        {            span = i - beg;            beg = i;            hashTable[s[i]] == 0;            if (span > maxspan)                maxspan = span;        }        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;}

结果

5

3