题目一

 

 解题思路

KMP算法详解

详解next数组

next[i] 就是使子串 s[0…i] 有最长相等前后缀的前缀的最后一位的下标。

总体来说解next数组和模板串匹配的过程很相似，触类旁通

代码模板

#include<iostream>
using namespace std;
const int N=1e5+10;
char p[N],s[N];
int m,n,ne[N];int main()
{cin>>n;for(int i=0;i<n;i++)cin>>p[i];cin>>m;for(int i=0;i<m;i++)cin>>s[i];ne[0]=-1;//构造模板串的next数组for(int i=1,j=-1;i<n;i++){while(j!=-1&&p[i]!=p[j+1])j=ne[j]; // 若前后缀匹配不成功// 反复令 j 回退，直至到 -1 或是 s[i] == s[j + 1]if(p[i]==p[j+1])j++;//匹配相等时，最长相等前后缀变长，最长相等前后缀最后一位变大ne[i]=j;    //令ne[j],以方便计算next【i+1】}for(int i=0,j=-1;i<m;i++){while(j!=-1&&s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++;if(j==n-1)//模板串匹配完成，第一个匹配字符下标为 0，故到 n - 1{printf("%d ",i-j);j=ne[j];// 回退到 ne[j] 可以保证 j 最大，即已经成功匹配的部分最长}}return 0;
}