kmp算法

kmp算法就是在一个字符串中寻找一个字串的过程。
设主串后面用m表示(长度为m)：a b a c a a b a c a b a c a b a a b b
模式串后面用n表示(长度为n)： a b a c a b
我们可以发现当进行到底6位的时候，与主串不同，现在我们应该去移动模式串，可是应该怎么移动呢？我们在第6位之前去找公共的前后缀，然后把前缀移动到后缀，这样就大大的节约了时间。可是应该怎样把前缀的位置移动到后缀并记录下来呢？用nx数组记录

void getnx()
{
    int i=0,j=-1;
    nx[0]=-1;
    while(i<l1)
    {
        if(j==-1||s1[i]==s1[j])
        {
            ++i;
            ++j;
            nx[i]=j;
        }
        else
            j=nx[j];
    }
}

接下来是写kmp算法
假设现在文本串s2匹配到 i 位置，模式串s1匹配到 j 位置
如果j = -1，或者当前字符匹配成功（即s2[i] == s1[j]），都令i++，j++，继续匹配下一个字符；
如果j != -1，且当前字符匹配失败（即s2[i] != s1[j]），则令 i 不变，j = nx[j]。意味着失配时，模式串s1相对于文本串s2向右移动了j - next [j] 位。

int kmp()
{
    int i=0,j=0,ans=0;
    while(i<l2)
    {
        if(j==-1||s2[i]==s1[j])
        {
            ++i;
            ++j;
        }
        else
            j=nx[j];
        if(j==l1)
        {
            ans++;
            j=nx[j];
        }
    }
    return ans;
}

本文地址：https://blog.csdn.net/sz0902/article/details/107877172