kmp：

KMP的主要目的是求B是不是A的子串，以及若是，B在A中所有出现的位置

写的很详细的大佬的博客：http://www.matrix67.com/blog/archives/115

 模板：

/*pku3461(Oulipo), hdu1711(Number Sequence)这个模板 字符串是从0开始的Next数组是从1开始的*/#include 
     
      #include 
      
       using namespace std;const int N = 1000002;int next[N];char S[N], T[N];int slen, tlen;void getNext(){    int j, k;    j = 0; k = -1; next[0] = -1;    while(j < tlen)        if(k == -1 || T[j] == T[k])            next[++j] = ++k;        else            k = next[k];}/*返回模式串T在主串S中首次出现的位置返回的位置是从0开始的。*/int KMP_Index(){    int i = 0, j = 0;    getNext();    while(i < slen && j < tlen)    {        if(j == -1 || S[i] == T[j])        {            i++; j++;        }        else            j = next[j];    }    if(j == tlen)        return i - tlen;    else        return -1;}/*返回模式串在主串S中出现的次数*/int KMP_Count(){    int ans = 0;    int i, j = 0;    if(slen == 1 && tlen == 1)    {        if(S[0] == T[0])            return 1;        else            return 0;    }    getNext();    for(i = 0; i < slen; i++)    {        while(j > 0 && S[i] != T[j])            j = next[j];        if(S[i] == T[j])            j++;        if(j == tlen)        {            ans++;            j = next[j];        }    }    return ans;}int main(){        int TT;    int i, cc;    cin>>TT;    while(TT--)    {        cin>>S>>T;        slen = strlen(S);        tlen = strlen(T);        cout<<"模式串T在主串S中首次出现的位置是: "<
       
        <
       
      
     

 

 

扩展kmp：

给出模板串S和串T，长度分别为Slen和Tlen，要求在线性时间内，对于每个S[i]（0<=i<Slen)，求出S[i..Slen-1]与T的

最长公共前缀长度，记为extend[i]（或者说，extend[i]为满足S[i..i+z-1]==T[0..z-1]的最大的z值）。

扩展KMP可以用来解决很多字符串问题，如求一个字符串的最长回文子串和最长重复子串。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;int cnt[1000005];char t[1000005],p[1000005];int Next[1000005],ex[1000005];void pre(char p[])   // next[i]: 以第i位置开始的子串 与 T的公共前缀{    int m=strlen(p);    Next[0]=m;    int j=0,k=1;    while(j+1