欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

kmp算法

程序员文章站 2023-12-30 21:56:52
KMP算法 KMP是一种字符串匹配算法。此算法的核心在于$kmp$数组以及它的求法。 (以下约定字符串下标从$1$开始) $\bm{kmp}$数组 定义$kmp$数组:$kmp_{a,i}$表示字符串$a$的前缀$a_{1\sim i}$的最长相同真前后缀的长度,即$kmp_{a,i}=\max\l ......

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

上一篇:

下一篇: