KMP 经典的串匹配算法

基本操作之子字符串查找：给定一段长度为N的文本和一个长度为M的模式（pattern）字符串，在文本中找到一个和该模式相符的子字符串。
可以很容易地拓展为找出文本中所有和该模式相符的字符串、统计该模式在文本中的出现次数、或者找出上下文（和该模式相符的子字符串周围的文字）的算法。
经典应用：查找单词，海量文本查找。。。

暴力子字符串查找算法

所谓暴力，就是所有可能的地方都比较一遍pattern

int search(string pat,string txt){
    int M = pat.size();
    int N = txt.size();
    for(int i = 0;i<=N-M;i++){
        int j;
        for(j = 0; j<M;j++)
            if(txt[i+j]!=pat[J])
                break;
        if( j==M )
            return i;
    }
    return N;
}

典型的字符串处理应用程序中，索引j增长的机会很少，因此该算法的运行时间与N成正比，最坏情况下，则需要~NM次字符比较。正常的英文文本可能不会出现这样的情况，但是二进制文本是完全有可能的。
还有一种实现比如显式回退

for( i = 0, j = 0; i<N && j<M; i++)
{
    if(txt[i] == pat[j]  j++;
    else{ i-=j;j=0;}
}

KMP字符串查找算法

基本思想：当出现不匹配时，就能直销一部分文本的内容，可以利用这些信息避免将指针回退到所有已知的字符之前。
但是要注意，在匹配失败时，如果模式字符串中的某处可以和匹配失败处的正文相匹配，那么就不应该完全跳过所有已经匹配的所有字符。
所以KMP算法的主要思想是提前判断如何重新开始查找，而这种判断只取决于模式本身。

那么我们需要计算字符串f每一个位置之前的字符串的前缀和后缀公共部分的最大长度（不包括字符串本身，否则最大长度始终是字符串本身）。

#define MAX_N 200005

class KMP{
public:
    bool match(char *T, char *P,int n, int m){
        buildNext(P, m);
        int i = 0, j = 0;
        
        while(j < m && i < n){
            if(j < 0 || T[i] == P[j]) { //若匹配
                i++; j++; //则携手并进
            }
            else{ // P右移, T不回退
                j = next[j];
            }
        }
        return (i - j) <= (n - m);        
    }

private:
    int next[MAX_N];
    void buildNext(char *P, int m){
        int t = next[0] = -1;
        int j = 0;
        while(j < m - 1){    //j来遍历next数组
            if(t < 0 || P[j] == P[t]){    //以前缀为目标进行匹配，没有相等字符串或者匹配成功+1
                j++; t++;
                next[j] =  (P[j] != P[t]) ? t : next[t];  //原本为next[j]=t;如果P[j]==P[t]的话，回溯到next[t]
            }
            else
                t = next[t];    //往前回溯，缩小子串的范围继续比较 
        }
        return;
    }
};