//注:文章是蒟蒻XZY一个字一个字地码出来的,图也是一笔一笔画出来的,要转载一定要说明出处(https://www.k-xzy.xyz)啊/(ㄒoㄒ)/~~!

1. 一些废话

首先说明,本文中的指针都不是真正的指针,指的是数组下标的编号。

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
——度娘

其实这算法简称叫做看毛片算法

2. 基本思想

问题:从字符串sup(长度为n)中找到字符串sub(长度为m)。

朴素算法:枚举字符串sub的第一个字符对应的sup中的字符的编号,再挨个比较。复杂度$O(n×m)$

kmp算法:其他都与朴素算法相同,但是它改进了“枚举字符串sub的第一个字符对应的sup中的字符的编号”这一过程,从而减小了复杂度。复杂度为$O(n+m)$

那么kmp的基本思想到底是什么呢?

如图,我们要匹配字符串sup、sub(在字符串sup里找sub),其中蓝色的表示这段区域里面的字符都相等(匹配成功),粉色表示那个位置的字符不同:

如果按照朴素的做法,这时候我们就应该把sub向右移动一位,再从头判断。

但我们kmp不会这样。它是怎么做的呢?

如图,假如这两块绿色区域内的字符串相同:

右移以后直接从对齐的绿色区域的后一位开始继续进行匹配判断。

这样就使得复杂度降低了。

根据势能分析可以得出复杂度是线性的,也就是$O(n + m)$的。

3. 具体实现

移动字符串很简单:移动字符串其实就是移动指针。

那么我们怎么得到深色区域呢?

预处理

设$next[i]$表示在sub中,区间$[0,i]$的最长的公共前缀后缀的长度(字符串的第一位下标为0)。

什么是最长的公共前缀后缀的长度

首先,前缀就是字符串的一个子串,子串的第一位是原字符串的第一位。

如原字符串为abcdabcd,那它的前缀有:a,ab,abc,abcd,abcda,abcdab,abcdabc,abcdabcd

后缀则反之。如原字符串依然为abcdabcd,那么它的后缀有:d,cd,bcd,abcd,dabcd,cdabcd,bcdabcd,abcdabcd

理解了这个,我们就能理解什么是最长的公共前缀后缀了。
它是一个字符串的前缀,同时也是该字符串的后缀。但它不能使字符串本身。
如abcdabcd中,最长的公共前缀后缀就是abcd
那它的最长的公共前缀后缀的长度就为4。

所以,对于字符串abcdabcd,它的$next$数组是这样的:

$next[0]=0,next[1]=0,next[2]=0,next[3]=0,next[4]=1,next[5]=2,next[6]=3,next[7]=4$

所以当匹配到sub的第i为不同时,此时深色区域的长度就是$next[i]$。

怎么得到next数组呢?

(图是网上找来的,出自:http://blog.csdn.net/yutianzuijin/article/details/11954939/)

我觉得有必要解释一下上面那个凌乱的图。

上面那一条$next[i]$是下面那一条中两个黑色部分分别放大得到的(放大指的是图片放大!!!注意图中对应的实线、虚线、箭头的区别!!!)。

下面那条中左边的黑色部分和右边的黑色部分是相同的,所以放大后都是得到的上面那条。

它表示的是:下面那条中的黑色部分的最长公共前缀后缀的长度是$next[next[i]]$!!!

假设我们现在已经求得$next[0]$、$next[1]$、……$next[i-1]$,分别表示长度为1到$i$的字符串的前缀和后缀最大公共长度,现在要求$next[i]$。

由上图我们可以看到,如果位置$i$和位置$next[i-1]$处的两个字符相同,那么$next[i]=next[i-1]+1$。

如果两个位置的字符不相同,我们可以将长度为$next[i-1]$的字符串继续分割,获得其最大公共长度$next[next[i-1]]$,然后再和位置i的字符比较。

这是因为长度为$next[i-1]$前缀和后缀都可以分割成上部的构造,如果位置$next[next[i-1]]$和位置i的字符相同,则$next[i]=next[next[i-1]]+1$。

如果不相等,就可以继续分割长度为$next[next[i-1]]$的字符串,直到字符串长度为0为止。

没看懂上面那个没关系,我也没看懂,鬼知道上面那几句话在扯什么。。。我从上面那个博客转载来的。。。

所以还是看代码吧

代码很简单,寥寥几行:

//这里sub的下标从0开始
for(int i=1,j=0;i<m;i++)//m表示sub的长度,j的值为next[i-1],nxt为next的缩写
{
    while(j&&sub[i]!=sub[j])j=nxt[j-1];
    //当j!=0且不符合条件时继续切割,至于为啥是j-1而不是j原因是下标是从0开始的
    if(sub[i]==sub[j])j++;
    //如果sub[i]==sub[j]则next[i]++
    nxt[i]=j;
}

实现了这个就很简单了。

在匹配字符串时,如果发现不匹配的字符就让指向sub的指针$j$改变为$next[j-1]$,直到$j$为0或者位置$j$的字符串匹配了。

为什么是$j=next[j-1]$呢?

回到上面的图中,当前不匹配位(红色)的编号为$j$,所以深色的区域的长度为$next[j-1]$。

至于结束匹配:当指向sup的指针$i$已经大于$n$(sup的长度)时,说明已经无法继续匹配了,匹配结束。

如果指向sub的指针$j$已经大于$m$(sub的长度)时,说明新找到了一个匹配的字符串。

具体看代码吧。

下面的代码中我没用变量$n, m$表示字符串长度。

$supl$表示字符串sup的长度,$subl$表示字符串sub的长度,$supi$表示sup的指针,$subi$表示sub的指针。

4. 例题&代码

都是模板题,思路我就不讲了。。。= ̄ω ̄=

1. 剪花布条 HDU – 2087

传送门= ̄ω ̄=

代码:

#include <bits/stdc++.h>
using namespace std;
char sup[1005],sub[1005];
int supl,subl,nxt[1005],supi,subi,ans;
int main()
{
    while(scanf("%s",sup),strcmp(sup,"#")!=0)
    {
        scanf("%s",sub),supl=strlen(sup),subl=strlen(sub);
        for(int i=1,j=0;i<subl;i++)
        {
            while(j&&sub[i]!=sub[j])j=nxt[j-1];
            nxt[i]=j+=sub[i]==sub[j];
        }
        for(ans=supi=subi=0;supi<supl;supi++)
        {
            while(subi&&sup[supi]!=sub[subi])subi=nxt[subi-1];
            subi+=sup[supi]==sub[subi];
            if(subi==subl)ans++,subi=0;
        }
        printf("%d\n",ans);
    }
    return 0;
}

2. Oulipo HDU – 1686

传送门= ̄ω ̄=

代码:

#include <bits/stdc++.h>
using namespace std;
int t,supl,subl,supi,subi,nxt[10005],ans;
char sup[1000005],sub[10005];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",sub,sup),subl=strlen(sub),supl=strlen(sup);
        for(int i=1,j=0;i<subl;i++)
        {
            while(j&&sub[i]!=sub[j])j=nxt[j-1];
            nxt[i]=j+=sub[i]==sub[j];
        }
        for(ans=subi=supi=0;supi<supl;supi++)
        {
            while(subi&&sup[supi]!=sub[subi])subi=nxt[subi-1];
            subi+=sup[supi]==sub[subi];
            if(subi==subl)ans++,subi=nxt[subi-1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

3. 【模板】KMP字符串匹配 LUOGU – 3375

传送门= ̄ω ̄=

代码:

#include <bits/stdc++.h>
using namespace std;
int supl,subl,nxt[1005];
char sup[1000005],sub[1005];
int main()
{
    scanf("%s%s",sup,sub),supl=strlen(sup),subl=strlen(sub);
    for(int i=1,j=0;i<subl;i++)
    {
        while(j&&sub[i]!=sub[j])j=nxt[j-1];
        nxt[i]=j+=sub[i]==sub[j];
    }
    for(int i=0,j=0;i<supl;i++)
    {
        while(j&&sup[i]!=sub[j])j=nxt[j-1];
        j+=sup[i]==sub[j];
        if(j==subl)printf("%d\n",i-j+2),j=nxt[j-1];
    }
    for(int i=0;i<subl;i++)printf("%d ",nxt[i]);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

ZQC · 2018年7月13日 4:36 下午

%%%

    XZYQvQ · 2018年7月13日 5:32 下午

    emmmm….
    您居然去雅礼了。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *