【算法】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; //最长相同前后缀长度为0
i++; //i后移
}
else
front = 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++;
}
else
front = 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;
}完.