KMP字符串匹配算法 学习笔记【KMP】【字符串】

作者: wjyyy 分类: KMP,字符串,学习笔记 发布时间: 2018-08-28 22:11

点击量:23

一、简介

    KMP是由Knuth、Morris和Prat发明的字符串匹配算法,它的时间复杂度是均摊\(O(n+m)\)。其实用Hash也可以做到线性,只不过Hash存在极其微小的难以避免的冲突。于是就有了KMP。

 

    KMP算法用作模式串匹配,可以找到一个长为\(m\)的模式串在一个长为\(n\)的主串中出现的次数和位置。

 

二、朴素算法(\(O(nm)\))

    实际上是枚举模式串在主串中出现的位置,然后一一比对,出现错误就停止,移动到下一位。连续匹配成功\(m\)次就说明模式串在主串中出现了。

 

    其实\(O(nm)\)是一个比较宽的上界,随机数据远没有这么慢。不过给出主串S="aaaaaaaaaaa",模式串T="aaab",就得每次匹配到最后才知道挂掉了。那么我们既然已经知道这样会挂掉,为什么还要重复匹配呢?这就是KMP要解决的问题。

 

三、KMP算法

    0.注意事项

    KMP算法中,字符数组下标是从1开始而不是0,这样会比较方便,在匹配的时候直接调用nxt数组就不用-1了,而且很直观。

    1.nxt数组(next)

    nxt数组是KMP算法的核心。

 

    nxt数组nxt[i]中存的是后缀字符与前缀字符相同的个数,且后缀字符不是前缀字符,也就是不能完全匹配自己。

 

    对于ababcab而言,它的nxt数组是

nxt[1] nxt[2] nxt[3] nxt[4] nxt[5] nxt[6] nxt[7]
a ab aba abab ababc ababca ababcab
0 0 1 2 0 1 2
没有后缀与前缀相同 没有后缀与前缀相同 前缀”a”=后缀”a”

前缀”ab”=后缀”ab”

注意不能完全匹配自己

没有后缀与前缀相同(失配直接=0) 前缀”a”=后缀”a” 前缀”ab”=后缀”ab”

    看上去很简单。但是它怎么求呢?当然,如果递推掌握的比较好,可以知道,如果T[i+1]==T[nxt[i]+1],那nxt[i+1]=nxt[i]+1。而失配了怎么办,是我们接下来要解决的问题。

 

    2.nxt数组的作用

    在上面我们提到了,KMP算法是减少了朴素算法的重复匹配,均摊下来每个字符只匹配了一次。在上面的表格中,我们看到了nxt数组处理出了模式串后缀与前缀匹配数。当我们用模式串匹配主串,在后缀失配时,在模式串里与后缀相同的就是我们预处理出的前缀了,因此我们只需要把模式串前缀挪到现在的位置来即可。这时我们会发现,中间可能跳过很多没有用,也就是安排匹配不上的状态,这就是KMP的优化。

 

    3.nxt失配的求法

    可以看出,求nxt数组,就是在用模式串匹配自己,且不匹配第一位。当我们发现T[i+1]与T[nxt[i]+1]失配时,比nxt[i]要次一点但是仍然与T[i]所在后缀相同的前缀就是nxt[nxt[i]]了。就是我们相当于退而求其次,“贪心地”按长度从大到小找一个最能匹配上后缀的前缀。

匹配不到的情况

    比如说

ababababc
        ↑

如果匹配到第8+1位时失配了,这时就去找第nxt[8]+1位,(nxt[8]=6)也就是第6+1位。此时发现还是不行,继续找第nxt[6]+1位……直到找到nxt[1]=0,退出循环,再看看第一位是否匹配,如果匹配,nxt[9]=1,否则nxt[9]=0。

 

重新匹配到的情况

abcaba
     ↑

这里匹配到第5+1位发现失配,去找nxt[5]+1=2+1,仍然不行,但是nxt[2]=0了,此时退出循环,发现T[1]=T[6],所以nxt[6]=1。

 

    其实情况还有很多很多种,这里只是列举了几种,想让nxt数组的求法变得更加形象一些。

 

四、KMP代码

#include<cstdio>
#include<cstring>
char s[1000100];
char t[1000100];
int nxt[1000100];
int f[1000100];
int main()
{
    scanf("%s",s+1);
    scanf("%s",t+1);
    int n=strlen(s+1);
    int m=strlen(t+1);
    for(int i=2,j=0;i<=m;++i)
    {
        while(j&&t[i]!=t[j+1])
            j=nxt[j];
        if(t[j+1]==t[i])
            ++j;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=n;++i)
    {
        while(j&&(j==m||s[i]!=t[j+1]))
            j=nxt[j];
        if(t[j+1]==s[i])
            ++j;
        f[i]=j;
        if(f[i]==m)
            printf("%d\n",i-m+1);
    }
    for(int i=1;i<=m;++i)
        printf("%d ",nxt[i]);
    return 0;
}

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【KMP算法学习笔记】 […]

/* */