【kmp算法】字符串匹配
一,解决问题
kmp算法解决的是字符串匹配的问题,具体来说假定我们要在主串s[ ] 中匹配模式串p[ ],找到匹配到的位置loc;
二,具体实现和演变过程
最自然的想法是暴力写法 (BF)枚举主串字符s[ i ] ,和模式串p[ j ]。一个一个匹配,如果匹配失败,i指针回退回起点,往前进一位,再次进行比较,知道匹配成功。
代码如下:
#include<bits/stdc++.h>
#define int long long
const int INF = 1e18 + 10,maxn = 1e5 + 10;
using namespace std;
char p[maxn],s[maxn];
int n,m;
signed main (){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>m>>(p + 1)>>n>>(s + 1);
for(int i = 1; i <= n; i++){
int j = 1;
while(s[i] == p[j] && j <= m){
i++;
j++;
}
if(j == m + 1) {
cout<< i - j + 1 << '\n';
}
i = i - j + 1;//回退
}
return 0;
}
时间复杂度是O(nm) 因为对于s[i],最多被比较m次,每次比较都会++指针,共有n个字符会被比较。
kmp算法就是通过一些方法减少了比较次数,减少了时间复杂度的做法。
具体来说,我们先想办法使得i指针不回退,首先,我们已经知道匹配失败的位置前面所有位置都是匹配成功的,假设匹配失败的前一个位置为j 那么匹配失败的位置为j + 1,因为j + 1匹配失败,那么我们需要向右滑动字符串p,此时假设有一个ne【】数组,记录了p[i] 使得 p[1,ne[j]] = p[j-ne[j]+1,j] 的值即最长相等真字串长度,那么由于p[1,j] 之前是匹配成功的,那么只需要将j 回退到p[1,ne[j]] = p[j-ne[j]+1,j] 即可,任然只需要比较p[j + 1] = s[i]。代码如下:
for(int i = 1,j = 0; i <= m; i++){
while(j && p[j + 1] != s[i]) j = ne[j];
if(p[j + 1] == s[i]) j++;
if(j == n){
cout<<i - n<<' ';
j = ne[j];
}
}
那么问题来了,如何确定ne【】数组,我们采取相同的策略,假定现在匹配前缀p[1,j] 和后缀 p[i- j + 1,i]如果匹配成功,只需将长度j++,(还记得ne【】数组的定义吗)如果匹配失败,只需要前后缀各自减少长度ne[j] 同理,现在匹配失败的位置是p[j + 1],那么只需回退j指针就能找到前一个p[1,j - ne[j]] 和 pi-ne[j]+1,i那么代码如下(j 表示的意义不仅是匹配位置,也有长度的意思,以为前缀表示为p[1,j]):
//ne数组的生成过程中,考察ne[i]和ne[i-1] i >= 2;
//完成ne[i-1]匹配后可以确定p[1,j] = p[i-j,i-1]
//那么如果p[i] != p[j+1]
//应该回退j舍弃部分p[1,j] 的后缀和 p[i-j,i-1] 的前缀
//回退到j = ne[j] (i-1前的ne数组都已完成维护)
//此时p[1,ne[j]] 是p[1,j] 的真子集并且p[1,ne[j]] = p[j-ne[j]+1,j]
//匹配过程
for(int i = 2, j = 0; i <= n; i++){
while(j && p[i] != p[j + 1]) j = ne[j];
if(p[i] == p[j + 1]) j++;
ne[i] = j;
}
那么完整的代码如下:
#include<bits/stdc++.h>
#define int long long
const int INF = 1e18 + 10,maxn = 1e6 + 10;
using namespace std;
char p[maxn],s[maxn];
int ne[maxn];
signed main (){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>(p+1)>>m>>(s+1);
//ne数组的生成过程中,考察ne[i]和ne[i-1] i >= 2;
//完成ne[i-1]匹配后可以确定p[1,j] = p[i-j,i-1]
//那么如果p[i] != p[j+1]
//应该回退j舍弃部分p[1,j] 的后缀和 p[i-j,i-1] 的前缀
//回退到j = ne[j] (i-1前的ne数组都已完成维护)
//此时p[1,ne[j]] 是p[1,j] 的真子集并且p[1,ne[j]] = p[j-ne[j]+1,j]
//匹配过程
for(int i = 2, j = 0; i <= n; i++){
while(j && p[i] != p[j + 1]) j = ne[j];
if(p[i] == p[j + 1]) j++;
ne[i] = j;
}
for(int i = 1,j = 0; i <= m; i++){
while(j && p[j + 1] != s[i]) j = ne[j];
if(p[j + 1] == s[i]) j++;
if(j == n){
cout<<i - n<<' ';
j = ne[j];
}
}
return 0;
}
/xin-xi-ji-zhu-fu-wu/kmpsuan-fa-zi-fu-chuan-pi-pei-7064.html