【算法】KMP字符串匹配算法

目录

一、暴力

二、KMP

2.1 思路

2.2 next数组

2.3 实现

2.4 例题

---

一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。
                                                                                                                                —— KMP

一、暴力

在进行字符串匹配时，暴力匹配是我们想到的最简单的方法，即将子串与主串当中的每一个子串进行匹配。如果当前子串不匹配，则回溯到主串中下一个子串的开头重新进行匹配

在最坏的情况下，暴力匹配的时间复杂度为O（N*M），N为主串长度，M为子串长度

---

二、KMP

2.1 思路

在上面的例子中我们可以注意到，在子串中，不匹配的字符'C'前面的子串似乎有一些规律

可以看到，这部分子串的前缀和后缀是相同的。如果我们能够将前缀移动到后缀的位置，是不是就能避免重复的比较了呢？

解释一下字符串的前缀和后缀：前缀就是从字符串开头到任意位置的一段字符串，后缀就是从字符串任意位置到字符串结尾的一段字符串

可以看到，通过这种方式，上面的箭头不需要向前回溯，下面的箭头也不需要回到子串的开头了，时间复杂度变为线性。这就是KMP算法的核心思想

但是我们怎样才能知道子串中每个位置的最长相同前后缀长度呢？这里就需要一个数组来维护了

2.2 next数组

next数组用于存放以下标i为结尾的子串最长相同前后缀长度，例如：

以下标0为结尾的子串"A"，只有自己一个字符，因此最长相同前后缀长度为0（此处前后缀不能为子串自身）

在代码实现中，我们可以用一个f和i，f代表最长相同前缀结尾位置，i代表最长相同后缀结尾位置

以下标1为结尾的子串"AB"，子串[f]和子串[i]不相同，且f=0，因此最长相同前后缀长度为0，i向后移动

以下标2为结尾的子串"ABA"，子串[f]和子串[i]相同，有最长相同前后缀"A"，因此最长相同前后缀长度为1，f和i都向后移动

以下标3为结尾的子串"ABAB"，子串[f]和子串[i]相同，加上上一步的结果，有最长相同前后缀"AB"，因此最长相同前后缀长度为2，f和i都向后移动

以下标4为结尾的子串"ABABC"，此时子串[f]和子串[i]不同，f回到next[f-1]下标处

此时f=0，但子串[f]和子串[i]还是不同，因此最长相同前后缀长度为0。i到达子串结尾，结束匹配

构建next数组的代码如下：

int ne[N];void buildNext(string &p)
{int front = 0; //front为最长相同前缀结尾int i = 1; //i为最长相同后缀结尾while(i < n){if(p[i] == p[front]) //前后缀结尾字符相同{ front++; //front后移ne[i] = front; //front++后，值正好为最长相同前后缀长度i++; //i后移}else //字符不相同{if(front == 0) //front在子串开头{ne[i] = 0; //最长相同前后缀长度为0i++; //i后移}elsefront = ne[front-1]; //修改front位置}}
}

2.3 实现

有了next数组，剩下的步骤也很简单：

当字符不匹配时

若j不在子串开头，则按照next[j-1]的数值修改j的位置，例如此处next[j-1]为2。某些情况中，在比较子串的第一个字符（j=0）时就已经不匹配了，此时不需要移动j，将i后移即可

于是将j移动到下标为2处，继续进行匹配。当字符匹配时，i和j各自后移即可

当j移动到子串结尾，说明子串匹配成功

2.4 例题

观察样例中可以发现，主串中可能存在多个与子串相同的字符串，我们需要把所有相同子串的起始位置都输出出来

#include <iostream>
#include <string>
#include <vector>
using namespace std;const int N = 100010;
const int M = 1000010;int ne[N]; //next数组
int n, m;void buildNext(string &p) //构建next数组
{int front = 0;int i = 1;while(i < n){if(p[i] == p[front]){front++;ne[i] = front;i++;}else{if(front == 0){ne[i] = 0;i++;}elsefront = ne[front-1];}}
}int main()
{string p;string s;cin >> n >> p >> m >> s;buildNext(p);vector<int> ans;int i = 0, j = 0;while(i < m) //当i没走到主串结尾时{if(s[i] == p[j]) i++, j++; //字符匹配，i、j后移else if(j > 0) j = ne[j-1]; //字符不匹配且j不在开头，根据ne数组修改位置else i++; //字符不匹配且j在开头，i后移if(j == n) //j走到子串结尾，说明子串匹配成功{ans.push_back(i-j); //放入i-j即子串在主串中的起始位置j = ne[j-1]; //修改j进行下一轮匹配}}for(auto i : ans){cout << i << " ";}return 0;
}

完.