KMP

KMP算法。其核心思想是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数，以达到快速匹配的目的。$KMP$算法的时间复杂度为$O(m+n)$，其中$m$是模式串的长度，$n$是文本串的长度

void zwpp(int n)//自我匹配
{
    p[1]=0;
    for(int i=1,j=0;i<n;i++)
    {
        while(j>0&&b[i+1]!=b[j+1])      //不匹配，回溯
            j=p[j];                     
        if(b[i+1]==b[j+1])              //j+1 匹配，j -> j+1
            j++;
        p[i+1]=j;                       //记录
    }
}
void KMP(int n)
{
    for(int i=0,j=0;i<n;i++)
    {
        while(j>=0&&b[j+1]!=a[i+1])     //不配配，回溯
            j=p[i];
        if(b[j+1]==a[i+1])              //匹配，b的下一个
            j++;
        if(j==n)                        //结束了，记录答案，回溯再找
        {
            ans++;
            j=p[i];
        }
    }
}
/*a,b字符串从下标1开始*/