数据结构——字符串匹配KMP

首先明确几个概念：

s[ ]: 主串

p[ ]: 模式串(用于匹配)

next[ j ]：以p[ j ]结尾的p字符串的前后缀最大匹配值,也是当p[ j+1 ]与s[ i ]不匹配时,j指针移动的下一位置。(需要预处理出来)

AcWing - 算法基础课

代码如下：

#include<iostream> using namespace std; const int N = 100100,M = 1000100; char s[M],p[N]; int ne[N]; int main() { int n,m; cin >> n >> p+1 >> m >> s+1; //求next数组 /* 求next数组和匹配过程类似 因为next[i]是以i结尾的(包括i)字符串的最大前后缀匹配值 然后这个过程相当于p串是前缀匹配,s串是后缀匹配,在每一个位置进行遍历 */ for(int i=2,j=0;i<=n;i++)//i=2开始是因为next[1]=0; { while(j&&p[i]!=p[j+1])j=ne[j]; if(p[i]==p[j+1])j++;//这里是两个p串 ne[i]=j; } //kmp for(int i=1,j=0;i<=m;i++) { while(j&&s[i]!=p[j+1])j=ne[j]; if(s[i]==p[j+1])j++; if(j==n) { //匹配上了一个输出开头下标 cout<<i-n<<" "; j=ne[j]; } } return 0; }