模板整理

整理遇到的几个比较难记的算法的模板。

KMP算法

KMP算法是字符串匹配算法，通常是在长字符串中对短字符串（模式串）进行匹配。
使用next数组对模式串的前缀表进行记录。
前缀表：当匹配失败时，将根据这个前缀表决定指针的位置。前缀表的目的是找到模式串中相等的前缀和后缀。
例如aabaaf,对于i=1, 模式串为aa,前缀和后缀都是a,因此next中存储的是1。
这个过程类似自己跟自己匹配。 前缀部分的next是我们先得到的。因此在用后缀跟前缀匹配的时候，一旦匹配失败，我们可以得出，当前后缀的前缀跟前缀的前缀是相同的。
比如 abadxxxxabab,next=0 0 1 0 xxxx 1 2 3,当我们计算最后一个b的时候匹配失败了。
此时我们要找到能够匹配aba的后缀的整个字符串的前缀。我们已经知道aba后缀对应相等的前缀了。其实就是next[i-1],也就是当前的j=3.
那么这个值除了已经匹配失败的j=3,还有前缀aba对应的next，也满足这个要求。通过不断的往前进行搜索，得到结果。可以把这个过程看成一棵树。

在haystack中搜索模式串的原理和上面是差不多的。

class Solution {
    void getNext(int *next,string needle){
        int n=needle.size();
        int j=0;
        next[0] = j;
        for(int i=1;i<n;++i){
            while(j>0&&needle[j]!=needle[i]){
                j=next[j-1];
            }
            if(needle[j]==needle[i]){
                j++;
            }
            next[i]=j;
        }
    }
public:
    int strStr(string haystack, string needle) {
        int n=haystack.size(), m=needle.size();
        int next[m];
        getNext(next, needle);
        int i=0,j=0;
        for(int i=0;i<n;++i){
            while(j>0&&needle[j]!=haystack[i]){
                j=next[j-1];
            }
            if(haystack[i]==needle[j]){
                j++;
            }
            if(m==j){
                return (i - m + 1);
            }
        }
        return -1;
    }
};