KMP算法 » 老官童鞋gogo的博客

KMP算法简介

算法来源

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

主要作用

KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

时间复杂度

$$ O(n+m) $$

$ n,m $分别表示字符串$ s_1,s_2 $的长度。

举例

两个字符串 $ s_1,s_2 $，$ s_1 $ 是文本串， $ s_2 $ 是一个模式串，要查找在$ s_1 $中$ s_2 $ 出现的位置。

方法1：暴力匹配

设$ i,j $分别为字符串$ s_1,s_2 $的指针，$ s1[i],s2[j] $分别表示字符串$ s_1 $和$ s_2 $当前正在比较的两个字符。

从$ 1 $ 到字符串$ s_1 $长度 $ len_{s1} $ 依次枚举，每枚举文本串的一个字符，就将 $ j $ 从 $ 1 $到字符串长度 $ len_{s2} $ 依次枚举，当s1[i]==s2[j]时，将i++,j++;，当a[i]!=a[j]时，令i=i-(j-1),j=0;，所以总共的复杂度为 $ O(len_{s1} len_{s2}) $

方法二：KMP算法

这种算法的时间复杂度为 $ O(n+m) $，比暴力算法优化了很多，具体的解释如下。

KMP算法的原理

基本原理

首先假设当前的字符串$ s_1 $枚举到了第 $ i $ 位，字符串 $ s_2 $ 枚举到了第 $ j $ 位。当第$ s1[i] $ 与$ s2[j+1] $ 相同时，继续i++,j++;，当两个字符失配时（即两个字符不相等的时候），将j跳回为$ next[j] $（什么是$ next[] $数组，后文会详细讲解，粗略解释为是重新开始字符串匹配的最佳位置，以省去暴力枚举的时间），也就是退回了$ j-next[j] $个位置，并重新开始匹配。

$ next[] $数组

作用

$ next[i] $ 表示在模式串中，在第$ i $个位置失配时，需要重新匹配的起点。而这个重新匹配的起点是什么？

假如说我的模式串为 $ a,b,c,a,b $ ，$ next[i] $表示从第$ 1 $位到第$ i $位中最长的相同前缀与后缀（除自身）的长度，例如$ next[3]=0,next[4]=1,next[5]=2 $，因为当$ i=3 $时，没有相同的前缀与后缀，当$ i=4 $时，相同的前缀与后缀为 $ a $，长度为$ 1 $，当$ i=5 $ 时，相同的最长的前缀与后缀为 $ a,b $长度为$ 2 $ 。那么当我们在第$ j+1 $位失配时，要回到第$ next[j] $位，因为此时我们将位置跳回了 $ next[j] $的位置后，模式串前面的字符对应关系没有改变，因为他们的后缀与前缀是相同的，改变的是后面的要比较的字符，而这种方法有恰好避免了漏掉字符串的问题，因为后缀都没有对应，整个字符串更是无法对应。如果还不能理解，如图：

举例来说，有一个字符串 $ s_1 = “BBC ABCDAB ABCDABCDABDE” $，判断里面是否包含另一个字符串 $ s_2 = “ABCDABD” $？

1、首先，用$ s_1 $的第一个字符和$ s_2$的第一个字符去比较，不符合，关键词向后移动一位。

2、重复第一步，还是不符合，再后移。

3、一直重复，直到$ s_1 $有一个字符与$ s_2 $的第一个字符符合为止。

4、接着比较字符串和搜索词的下一个字符，还是符合。

5、遇到$ s_1 $有一个字符与$ s_2 $对应的字符不符合。

6、这时候想到的是继续遍历$ s_1 $的下一个字符，重复第1步。

7、其实这是很不明智的，因为此时 $ ”ABCDAB” $已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与$ D $不匹配时，你其实知道前面六个字符是$ ”ABCDAB” $。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置“移回已经比较过的位置，继续把他向后移，这样就提高了效率。而帮助我们移动到最合适的位置的，就是$ next[i] $数组，这就是这个数组的作用。

部分匹配值表示$ next[i] $的值

8、已知空格与$D$不匹配时，前面六个字符$ ”ABCDAB” $是匹配的。查表可知，最后一个匹配字符$B$对应的”部分匹配值”为2，因此我们只需要让模式串$ s_2 $的下标移动到对应下标为2的位置，也就是C，此时$ s_1 $的下标还是保持不变，在空格处，这样就避免了$ s_1 $下标回溯到第6步了，这样就大大减少了$ s_1 $的比较次数。

9、因为空格与$Ｃ$不匹配，搜索词还要继续往后移。这时已匹配的字符串为$”AB”$，最后一个匹配字符$B$对应的”部分匹配值”为$0$。因此我们只需要让模式串$s_2$的下标移动到对应下标为0的位置，也就是$A$，此时$ s_1 $的下标还是保持不变。

10、因为空格与$A$不匹配，并且此时并没有匹配的字符，因此只能继续后移一位。

11、然后逐位比较，直到发现$C$与$D$不匹配。

12、因为$C$与$D$不匹配，这时已匹配的字符串为$”ABCDAB”$，最后一个匹配字符$B$对应的”部分匹配值”为$2$。因此我们只需要让模式串$s_2$的下标移动到对应下标为$2$的位置，也就是$C$，此时$s_1$的下标还是保持不变。

13、然后逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。

这就是$ next[] $ 数组的作用。

构建

$ next[i] $数组的初始状态为$ next[0]=next[1]=0 $因为当字符串中没有或者是只有一个字符的时候，除了它的本身，不会再有其他的前缀或者后缀，所以它们的值自然为$ 0 $。然后，我们从$ 1 $ 开始枚举$ s_2 $，设$ j $ 表示正在处理的前缀的位置，当s2[j+1]==s2[i]时，即下一位能够与i相匹配，则j++，当两个不能匹配的时候时，将$ j $跳回到$ next[j] $,原理与上面类似，但是我们的目的是要保证前缀与后缀相同，然后继续枚举，如果$ j $ 调回后仍然与后缀对不上，那么我们将$ j $再次跳回，直到满足s2[j+1]==s2[i]或者是j==0，即跳回了最初的位置，说明没有前缀与后缀相同。最后将$ next[i] $赋值为 $ j $。

$ next[] $数组代码

scanf("%s",s1+1);
scanf("%s",s2+1);
int len1=strlen(s1+1),len2=strlen(s2+1),j=0;
nxt[0]=nxt[1]=0;
for(int i=2;i<=len2;i++)
{
    while(j&&s2[j+1]!=s2[i])//字符串内部失配时，将前缀指针调整到上一个与它匹配的位置
        j=nxt[j];
    if(s2[j+1]==s2[i])//如果能匹配，将指针后移
        j++;
    nxt[i]=j;
}

搜索

按照上面的方法比较即可。详情看代码注释：

搜索代码

for(int i=1,j=0;i<=len1;i++)
{
    while(s1[i]!=s2[j+1]&&j)//对比字符串s1和s2，如果失配就将j跳回到next[j]
        j=nxt[j];
    if(s1[i]==s2[j+1])//如果成功匹配，就匹配下一位
        j++;
    if(j==len2)
    {
        printf("%d\n",i-len2+1);//完全匹配后，输出此时字符串s1的初始位置。
        j=nxt[j];//向后移动一位，重新开始寻找
    }
}

代码

来源：洛谷：P3375 【模板】KMP字符串匹配

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
char s1[10000001],s2[10000001];
int nxt[10000001];
int main()
{
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    int len1=strlen(s1+1),len2=strlen(s2+1),j=0;
    nxt[0]=nxt[1]=0;
    for(int i=2;i<=len2;i++)
    {
        while(j&&s2[j+1]!=s2[i])
            j=nxt[j];
        if(s2[j+1]==s2[i])
            j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=len1;i++)
    {
        while(s1[i]!=s2[j+1]&&j)
            j=nxt[j];
        if(s1[i]==s2[j+1])
            j++;
        if(j==len2)
        {
            printf("%d\n",i-len2+1);
            j=nxt[j];
        }
    }
    for(int i=1;i<=len2;i++)
    {
        printf("%d ",nxt[i]);
    }
    return 0;
}