3.Longest Substring Without Repeating Characters(string; HashTable)

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

思路I：使用动态规划，记住当前最长 substring的长度及开始的字符位置，这样时间复杂度最坏O(n2)，最好情况下O(n)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s=="") return 0;
        
        //状态信息
        int maxLen = 1;
        int curLen = 1; 
        int startIdx = 0; 
        
        int i, j;
        for(i = 1; i < s.length(); i++){
            for(j = startIdx; j < i; j++){
                if(s[j] == s[i]){
                    //更新状态信息
                    if(curLen > maxLen) maxLen = curLen;
                    startIdx = j+1; 
                    curLen = i - startIdx + 1;
                    break;
                }
            }
            if(j == i){
                curLen++;//更新状态信息
            }
            
            if(curLen > maxLen) maxLen = curLen;//更新状态信息
        }
        return maxLen;
    }
};

思路II：Hash Table。以128个ASCII字符作为key，以字符最后出现的位置为value，用一个数组实现哈希表。时间复杂度O(n)。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        const int size = 128;
        int hashTable[size]; //save the latest occurence of 128 ACSII characters
        int start=0; //start index of current substring without repetition
        int len; //length of current substring without repetition
        int maxLen=0;
        
        for(int i = 0; i < size; i++){
            hashTable[i] = -1; //initialized as -1
        }
        
        for(int i = 0; i < s.length(); i++){
            if(hashTable[s[i]]>=start){
                len = i-start;
                if(len>maxLen){
                    maxLen = len;
                }
                start=hashTable[s[i]]+1;
            }
            hashTable[s[i]]=i;
        }
        
        //check final substring
        len = s.length()-start;
        if(len>maxLen){
            maxLen = len;
        }
       
        return maxLen;
    }
};

如果是求最长重复子串（子字符串R 在字符串L 中至少出现两次，则称R 是L 的重复子串。）

KMP法

KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法的时间复杂度为O(m+n)。
一个极端的例子是：在S=“AAAAAA…AAB“(100个A)中查找T=”AAAAAAAAAB”, 简单匹配算法每次都是比较到T的结尾，发现字符不同，然后T的下标回溯到开始，S的下标也要回溯相同长度后增1，继续比较。如果使用KMP匹配算法，就不必回溯。

设在字符串S中查找模式串T，若S[i]!=T[j]，那么T[j]的模式函数值next[j]告诉我们下一步应该比较哪两个字符。
next[j]的求法：

如果T[j]的前面k个字符与开头的k个字符相等，

• 如果T[j]不等于第k+1个字符T[k]，那么next[j]=k 意义：S[i]之前的k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[i]和T[k]
• 如果T[j]等于第k+1个字符T[k]
  • 如果T[j]=T[0]，那么next[j]=-1 意义：虽然S[i]之前的k个字符与T中的开始k个字符已经间接比较相等了，但第k+1个字符不等，所以要重新开始比较；又因为S[i]与T[0]间接比较过不相等，所以下一次比较S[i+1]和T[0]
  • 如果T[j]!=T[0]，那么next[j]=0 意义：下一次比较S[i]和T[0]

如果T[j]的前面k个字符与开头的k个字符不相等，

• 如果T[j]=T[0]，那么next[j]=-1 意义：虽然S[i]之前的k个字符与T中的开始k个字符已经间接比较不相等，所以要重新开始比较；又因为S[i]与T[0]间接比较过不相等，所以下一次比较S[i+1]和T[0]
• 如果T[j]!=T[0]，那么next[j]=0 意义：下一次比较S[i]和T[0]

KMP方法在查询的时候，S不用回溯，是因为当比较到有不同的字符时，next[j]告诉了你前面有多少字符与开头的字符相等，直接比较S[i]和T[next[j]]（如果next[j]=-1，比较S[i+1]和T[0]）。

计算模式串：
例1：T=”abCabCad”
答案：next = [-1 0 0 -1 0 0 -1 4]
解答：
next[3] = -1的原因：(1)首先，T[3]==T[0]; (2)其次，k=1时T[2]!=T[0], k=2时T[1]+T[2]!=T[0]+T[1]，即j前面的k个字符与开头k个字符不等。
next[6]=-1的原因：(1)T[6]==T[0]；(2)虽然j前面的3个字符与开头3个字符相等，但T[3]==T[6]

例2：T=”AAAAAAAAAB”
答案：next = [-1-1-1-1-1-1-1-1 -1 8]
解释：next[9] = 8 告诉我们，当S[m]!= T[9]时，下次查询S[m]和T[8]

求最长重复子串：next模式串求法有不同，next[j]表示在j之前重复字符串的长度，无论next[j]是否等于next[k]

int getNext(char *str,int *next)
{
    int len=strlen(str);
    int index=0;
    int k=-1;
    next[0]=k;
    int max=0;

    while (index<len)
    {
        if (k==-1 || str[index]==str[k]) //当前字符与前k+1个字符都相等，更新下一个字符的next值
        {
            next[++index]=++k; //next[下一个字符]=k+1
            if (k>max)//更新最长的重复字串
            {
                max=k;
            }
        }
        else 
            k=next[k]; //不相等时，next[k]告诉下一个比较的字符
    }

    return max;
}

int main()
{
    char str[50];//输入字符串
    cin>>str;
    int max=0;//最大的字串
    int nextMax;//接受getNext函数中返回的最大值
    int index;
    int maxIndex;//保存最大的字串起始位置
    int len=strlen(str);
    //将一个字符串从开始一直减少到只剩一个字符，通过这个取得最小字串
    for (index=0;index<len-1;index++)
    {
        int *next=new int[len-index];//取得next在这没用
        nextMax=getNext(str+index,next);//每次从str+index开始
        if (nextMax>max)
        {
            max=nextMax;
            maxIndex=index;
        }
    }
    
    cout<<"最长字串： ";
    for (index=0;index<max;index++)
    {
        cout<<str[index+maxIndex];
    }
    cout<<endl;
    
    return 0;
}