KMP算法

模板kmp就是两个串进行匹配判断p串是不是s的一个子串..下面讲讲匹配的过程--其实就画一幅图,说真的想清楚就不难了~

注意中p画在t右边图的是一个不匹配的一个元素~仔细看看就懂了
下面讲讲kmp循环节问题和kmp匹配子串问题.因为博主只是单纯的理解算法的用处,所以不会讲很多深奥的东西,毕竟菜.
1.循环节:
先给大家解释下,循环节怎么求的,到i的最小循环节必定是i-next[i]否则不存在,上面讲了next[i]的含义,下面还是画图解释一下

2.检测子串:
结合图一就好了.
求next数组代码,假如你看懂了图一就会了

void get_next()
{
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1]) j=net[j];
        if(s[i]==s[j+1]) j++;
        net[i]=j;
    }
}