KMP算法

介绍：

  • KMP算法是一种字符串匹配算法，用来高效匹配字符串子串问题。
  • 一般的做法就是一个一个试，时间复杂度为O(n * m)，这太大了，因此我们在大规模字符串的匹配时我们使用KMP算法就能将时间复杂度降到O(n+m)，这是显著的提升。
  • KMP算法里面会涉及许多其他概念，如前缀表(或next表)，最长相同前后缀等概念，后面会从最基础的概念开始，一步一步讲解这里面的概念。
  • 如果下面的讲解没看懂，也可以先把概念了解了，去看看B站上面的视频演示，视频加博客的学习可以加深印象。
  • 参考视频：最浅显易懂的 KMP 算法讲解 ，跟人认为这个视频还是比较优质的，本篇博客的写作思路要源于此。

概念解释：

KMP算法的思想：

  • 我们期望不同于传统方法不断回退i 来达到匹配字符串的目的，因此我们KMP算法里面i是不回退的，一直往后走，那我们又该怎么实现匹配呢？
  • 既然我们的i不会退但不代表我们的j不能回退，因此我们要找到一种回退方法，来使得我们的回退再匹配是有意义的，这就引出了我们的KMP算法里面的前缀表。

前后缀：

  • 前缀就是从开头开始的连续子串，不包括空字符串和整个字符串。
  • 后缀就是从末尾开始的连续子串，不包括包括空字符串和整个字符串。
  • 最长相同前后缀 ：字面意思，就是我们要找到所有前后缀里面，最长且相等的那一个（后面讲解递推求法）

前缀表：

  • 我们的匹配字符串里面的每个位置上都有一个以其为结尾的最长相同前后缀的长度
  • 1
    2
    3
    4
    5
    6
    7
    8
    aabaa 
    01012  这就是一个前缀表
    只有一个a时，没有前后缀
    aa  前后缀最长且相等为1,都是a
    aab  显然没有相等的前后缀 ，为 0
    aaba  通过观察得到，前后都有一个a，所以为 1
    aabaa  前后缀里面，aa和aa完全相同，所以为 2
    因此就生成了我们aabaa的前缀表

详细实现细节：

原理讲解：

假如我们已经有了前缀表

  • 我们在匹配时，就可以一直往前走，根据我们m的前缀表来对匹配字符串进行跳转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
演示如下：
 aafaabaa
 aabaa  匹配字符串
[01012] 前缀表
我们设置两个指针i，j分别对应text和pattern
第一轮：符合，i++，j++
第二轮：符合，i++，j++

第三轮：不符合，于是我们就要对pattern进行挪位置，但本身没法来挪，于是我们来改变j，以此来实现对位置的改变。
于是我们用前缀表来挪动
已知第三轮匹配的是 b 字母，其对应的前缀表是0，因此我们的j要跳转到pattern的0位置 
于是：j=profix[j-1] //j=1
aafaabaa
 aabaa
[01012]
但是为什么是j=profix[j-1] 呢？
已知我们当j走到某个位置的时候，j之前的内容和text的对应部分是完全相同的，不然我们早都跳转了
既然我们已经生成了前缀表，这时候就说明我们该前缀表前面的部分前后缀相同
以这题为例:
aafaabaa
 aabaa
[01012]
我们发现，f 前面的部分，为aa，第二个a对应的前缀表大小为1，如果我们跳转，就会发现，在f前面的那个a就会和我们pattern的第一个a，就对上了，为什么会对上呢，因为前缀表本身的意义就是前缀后缀相同，在f前面的部分，我们直接通过前缀表的跳转，就实现了把错误匹配字母前面的部分的前后缀直接就对上了，这就是匹配的核心，如果等于j=0还没有匹配上，就说明当前匹配失败，i++，继续往后面匹配。

第四轮：我们发现还是没办法匹配，但是我们还可以实现挪动，
于是第四轮结果：j=profix[j-1] //j=0
aafaabaa
  aabaa
 [01012]
第五轮：无法匹配且j=0，因此i++，继续往后面匹配
aafaabaa
   aabaa
  [01012]
第六轮：发现可以匹配，i++，j++。
后面就可以匹配了，我们就是靠这种方式来实现字符串的匹配，最后返回i-j+1，就是匹配字串的开始
  • 通过对前面的分析，我们可以发现，我们的i一直在往后面跳转，没有回退，只通过前缀表的跳转来实现pattern的挪动
    该部分演示代码 ：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int i=0;
int j=0;
while(i<len1){
    if(text[i]==pattern[j]){
    4i++; 
    4j++;
    }
    else if(j>0) j=profix[j-1];
    else i++;
    if(j==len2){
    4cout<<i-j+1<<"\n";
    4j=profix[j-1];
4}
}
  • 这里面的代码思路就是我们上面的讲解思路。
  • 下一个问题就是实现前缀表的生成。

生成前缀表

  • 我们要知道，前缀表的生成是一个求前后缀的过程，从第一个字母开始，到后面最后一个位置，每移动一个位置，就求一遍前面所有的字母的最长相等前后缀
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    讲解如下：
    假如给定一个字符串，求其前缀表，我们非暴力求解过程如下(暴力求解就是定义双指针一个一个试)：
    依旧是例题代码：
    aabaa  以这个为例
    当长度为1的时候，不存在前后缀，profix[0]=0
    所有长度为1时，直接可以默认为0，从2开始，后面的都通过一套流程来生成
    依旧经典双指针，一个指引现在我们pattern的位置，一个指引前缀
    curlen代表现在匹配的前后缀的长度，i对应我们现在指引的位置(用for来实现)
    curlen初始定义为0
    i从1开始
    接下来，先看patten[i]和pattern[curlen]匹不匹配，分为下面两种情况
    匹配：就把curlen++，并且profix[i]=curlen，注意这里要先加在赋值，索引问题
    不匹配：判断时候为0，如果为0，就证明一点都没法匹配，profix[i]=0
    444如果不为0，我们就往前推，curlen=profix[curlen-1]
    444为何呢？
    我们已经推出了前面的前缀表，因此curlen前一个位置的前缀长我们是知道的,
    我们通过查表的方式，就可以将当前curlen的位置，跳转到和curlen目前长度里面前后缀相同的地方的下一   个，来个例子演示一下
    abcabacdaabaa    假设当前i到了第12个位置
    00012100112      curlen当前也到了第3个位置
    发现下一个刚好不能匹配 于是我们来跳转，curlen=profix[curlen-1] curlen=2
    跳转后我们发现当前curlen前面的部分和i前面的部分是完全相同的，为什么呢，因为本身前缀表里面就代表   的是前后缀关系，我们跳转后就发现前后缀就直接对上了，这大大提高了我们的查找效率,我们按照这样的顺    序一个一个往后推，知道前缀表的生成

代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
int profix[1000005];
string text,pattern;
int main(){
    cin>>text>>pattern;
    //求前缀表
    int len1=text.size();
    int len2=pattern.size();
    int curlen=0;
    for(int i=1;i<len2;i++){
        while(curlen > 0 && pattern[i] != pattern[curlen]) curlen = profix[curlen - 1];4
44if(pattern[i] == pattern[curlen]) curlen++;
        profix[i] = curlen;
    }
    //字符串匹配
    int i=0;
    int j=0;
    while(i<len1){
    4if(text[i]==pattern[j]){
    44i++;
    44j++;
    4}
    4else if(j>0) j=profix[j-1];
    4else i++;
    4if(j==len2){
    44cout<<i-j+1<<"\n";
    44j=profix[j-1];
44}
4}
4//输出前缀表内容
4for(int i=0;i<len2;i++) cout<<profix[i]<<" ";
    return 0;
}