kmp模板

#include<stdio.h>int a[1000010],b[10010];// a是目标字符串,b是匹配字符串int next[10010]; // 当匹配串a失配的时候，next数组对应的元素指导应该用a串的哪个元素进行下一轮的匹配int n,m;// n是目标串的长度， m是匹配串长度。void getNext(){    int j,k;    j=0;    k=-1;    next[0]=-1;    while(j<m)    {         if(k==-1||b[j]==b[k])        {            j++;            k++;            if(b[j] != b[k])// 解决特殊情况例如匹配串为ccccccccd            {                next[j] = k;            }            else                next[j] = next[k];        }        else k=next[k];    }}//返回首次出现的位置int KMP_Index(){    int i=0,j=0;    getNext();    while(i<n && j<m)    {        if(j==-1||a[i]==b[j])        {            i++;            j++;        }        else j=next[j];    }    if(j==m) return i-m+1;    else return -1;}int KMP_count()  //包含子串个数{    int ans=0;    int i,j=0;    if(wlen==1&&tlen==1)    {        if(W[0]==T[0])return 1;        else return 0;    }    getNext();    for(i=0;i<tlen;i++)    {        while(j>0&&T[i]!=W[j])          j=next[j];        if(W[j]==T[i])j++;        if(j==wlen)        {            ans++;            j=next[j];        }    }    return ans;}