KMP算法
KMP算法就是在一个大长的字符串里找小的字符串的算法。
// 字符串匹配之暴力法
int S[N],p[M];
for(int i = 1;i<=n;i++){ // 遍历从i开始的字符有没有可能匹配上
bool flag = true;
for(int j = i;j<=m;j++){
if(S[i] != p[j]){
flag = false; // 已经出现没有匹配上的了
break;
}
}
}
KMP算法就是将j指针每次移动一个改变成每次移动最长公共子串个长度,这样就能极大的减少比较次数
#include <iostream>
using namespace std;
const int N = 10e5+10,M = 10e6+10;
char s[N],p[M];
int n,m;
int main(){
cin >> n >> s+1 >> m >> p+1; // 输入的匹配串和模式串都是从下标为1开始输入，下标为0的单元等同于浪费了，不过无所谓
// 求ne[]数组
for(int i=2,j=0;i<=m;i++){
while(j && s[i]!=p[j+1]) j = ne[j];
if(j && s[i]!=p[j+1]) j++;
ne[j] = j;
}
// KMP匹配
for(int i = 1,j = 0;i<=n;i++){ // 遍历匹配串的每一个字母,j是输入串的指针
// 匹配失败的情况
while(j && s[i]!=p[j+1]) j = ne[j]; // j往回回溯
// 匹配成功
if(j && s[i]!=p[j+1]) j++;
if(j == m){ // 满足匹配条件后，打印开头下标
printf("%d",i-m);
j = ne[j];
}
}
return 0;
}
