KMP算法详解_牛客博客

##写在前面：

欢迎转载，转载请在文章显眼处注明出处：

https://blog.nowcoder.net/grcyh

起源

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

                                                                                                                                                                                                                                                ——百度百科

前置知识：

1. 输入输出

2. 数组

3. $for$ 循环

模式串匹配的概念：

模式串匹配，就是给定一个需要处理的文本串和一个需要在文本串中搜索的模式串，查询在该文本串中(一般文本串应远大于模式串)，模式串的是否出现过，出现的次数和出现的位置等。

朴素算法：

首先要理解，朴素的单模式串匹配大概就是枚举每一个文本串元素，然后从这一位开始不断向后比较，每次比较失败之后都要从头开始重新比对，那么如果模式串和文本串是类似于这样的：模式串 $aaaab$ ，文本串是 $aaabaaabaaab$ ，如果是这样的话，我们设模式串长度为 $m$ ，文本串长度为 $n$ ，那么朴素的暴力算法就会被卡成 $O(nm)$ ，于是就有了那三个家伙大佬的 $KMP$ (然而并不认识他们是谁233)，下面我们就要讲 $KMP$ 了，准备好！

KMP：

在朴素算法中，我们每次匹配失败都不得不放弃之前所有的匹配进度，因此时间复杂度很高，而 $KMP$ 算法的精髓就在于每次匹配失败之后不会从模式串的开头进行匹配，而是根据已知的匹配数据，跳回模式串一个特定的位置继续进行匹配，而且对于模式串的每一位，都有一个唯一的“特定跳回位置”，从而节约时间。

比如我们考虑一组样例：

模式串：abcab
文本串：abcacababcab

首先，前四位按位匹配成功，遇到第五位不同，而这时，我们选择将模式串向右移三位，或者可以理解为移动到模式串中与失配字符相同的那一位。即我们将两个已经遍历过的模式串字符重合，因此可以不用一位一位地移动，而是根据相同的字符来实现快速移动。

模式串：   abcab
文本串：abcacababcab

但有时不光只会有单个字符重复：

模式串：abcabc
文本串：abcabdababcabc

当我们发现在第六位失配时，我们可以将模式串的第一二位移动到第四五位，因为它们相同 $emmmmmm$

模式串：   abcabc
文本串：abcabdababcabc

那么现在读者应该多少有些明白了， KMP 节约时间就在于用一个特定的位置来确定当某一位失配时，我们可以将前一位跳跃到之前匹配过的某一位。我们把这个特定的位置叫做失配指针(当然本人习惯这么叫，你们也可以叫什么失败指针之类的，都无所谓)。

n个指针，即为一个数组。

首先我们的失配数组应当1建立在模式串意义下，而不是文本串意义下。因为模式串长度小于文本串，要更加灵活，在失配后换位时，可以更加灵活的处理。

那么怎么找到这个位置呢？
在模式串s1中，对于第i个位置，它的失配指针应当指向一个位置j，满足：

1. $j \leq i$
2. $s1[i]==s1[j]$
3. 在 $j!=1$ 时理应满足 $s1[1]$ 至 $s1(j-1)$ 分别与 $s(i-j+1)$ 至 $str1(i-1)$ 按位相等

我们也可以从前后缀的角度来理解失配数组(前后缀是什么就不说了吧，应该大家都知道)：

这里定义真前缀和真后缀：对于一个字符串 $s_i$ 到 $s_j$ ，任意的 $s_x$ 到 $s_j$ 都是这个字符串的真前缀 $(i < x \leq j)$ ，同理，真后缀大家就都懂了吧？

那么，这里位置 $i$ 失配数组的值就是模式串 $s1_1$ 到 $s1_i$ 的最大公共真前缀和真后缀的长度。。有点绕？？ $emmmmm$ ……举个栗子(后面我们把失配数组定义为 $kmp$ 数组)

以字符串 $"abcdabd"$ 为例，
"a"的真前缀和真后缀都为空集，共有元素的长度为0，因此，kmp[1]=0；
"ab"的真前缀为[a]，真后缀为[b]，共有元素的长度为0，因此，kmp[2]=0；
"abc"的真前缀为[a, ab]，真后缀为[bc, c]，共有元素的长度0，因此，kmp[3]=0；
"abcd"的真前缀为[a, ab, abc]，真后缀为[bcd, cd, d]，共有元素的长度为0，因此，kmp[4]=0；
"abcda"的真前缀为[a, ab, abc, abcd]，真后缀为[bcda, cda, da, a]，共有元素为"a"，长度为1，因此，kmp[5]=1；
"abcdab"的真前缀为[a, ab, abc, abcd, abcda]，真后缀为[bcdab, cdab, dab, ab, b]，共有元素为"ab"，长度为2，因此，kmp[6]=2；
"abcdabd"的真前缀为[a, ab, abc, abcd, abcda, abcdab]，真后缀为[bcdabd, cdabd, dabd, abd, bd, d]，共有元素的长度为0，因此，kmp[7]=0。

即我们的操作只是针对模式串的前缀--−−毕竟是失配指针，失配之后只有可能是某个部分前缀需要“快速移动”。

然后利用 $kmp$ 数组进行字符串匹配即可(如果还不懂的话看代码吧)。

代码实现

在文本串中找模式串：

//其中k可以看做表示当前已经匹配完的模式串的最后一位的位置，你也可以理解为表示模式串匹配到第几位了 
k=0;            //把计数器清零。
for(int i=0;i<n;++i) {
    while(k&&s1[i]!=s2[k]) k=kmp[k];              
    //匹配失败就沿着失配指针往回调，跳到模式串的第一位就不用再跳了。
    if(s1[i]==s2[k]) ++k;                  //匹配成功那么匹配到的模式串位置+1。                                         
    if(k==m) printf("%d\n",i-m+2);         //找到一个模式串，输出位置即可。
  }

求失配数组：

//即为一个模式串自身匹配自身的过程，刚刚说过失配数组是建立在模式串的意义下的，跟与文本串匹配思路一样
int n=strlen(s1),m=strlen(s2);
  for(int i=1;i<m;++i) {
    while(k&&s2[i]!=s2[k]) k=kmp[k];
    if(s2[i]==s2[k]) kmp[i+1]=++k;
  }

时间复杂度：

最坏时间复杂度为O $(n+m)$ (从代码上看挺显然的吧)

模板题

洛谷的一道模板题：

https://www.luogu.org/problemnew/show/P3375

完整代码：

#include
#include
#define maxn 1000007
using namespace std;
int k,kmp[maxn];
char s1[maxn],s2[maxn];
int main() {
  scanf("%s%s",s1,s2);
  int n=strlen(s1),m=strlen(s2);
  for(int i=1;i<m;++i) {
    while(k&&s2[i]!=s2[k]) k=kmp[k];
    if(s2[i]==s2[k]) kmp[i+1]=++k;
  }
  k=0;
  for(int i=0;i<n;++i) {
    while(k&&s1[i]!=s2[k]) k=kmp[k];
    if(s1[i]==s2[k]) ++k;
    if(k==m) printf("%d\n",i-m+2);
  }
  for(int i=1;i<=m;++i) printf("%d ",kmp[i]);
  printf("\n");
  return 0;
}

后记：

$KMP$ 算法的精髓在于 $kmp$ (有些人也叫它 $next$ 数组)数组，尤其是那个关于前后缀的那块思路很重要，还需要大家多做题，慢慢的感悟，扩展 $KMP$ 还没有学(先留个坑)，等以后学了再补。