如果s[i] != p[j+1] 时,令k=ne[j] ,k就是使最长前缀=后缀长度移动的最短距离
由匹配数组ne的含义可知 p[1..k] = p[j-k+1..j]

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;

int n,m;
char p[maxn],s[maxn]; //p为模板串，s为模式串
int ne[maxn]; 

void getnext(){
	 for(int i=2,j=0;i<=n;i++){
	 	//因为next[i]的定义是非本身的最大后缀等于最大前缀，即必须要小于i，所以next[1]必须等于0，i就只能从2开始循环了。
	 	 while(j&&p[i]!=p[j+1]){//j和i错开一位每次拿j+1的值与i比 
	 	 	   j=ne[j];//如果一直匹配失败，就一直返回直到连首字符都不匹配 
		  }
		  if(p[i]==p[j+1]){
		  	 j++;//匹配了就向后移一位 
		  }
		  ne[i]=j;
	 }
}

int main(){
	cin>>n>>p+1>>m>>s+1;//下标都从一开始计数 
	getnext();//求next数组 
	for(int i=1,j=0;i<=m;i++){
		while(j&&s[i]!=p[j+1]){//匹配的过程基本与求next数组一样 
			j=ne[j];
		}
		if(s[i]==p[j+1]){
			j++;
		}
		if(j==n){
			cout<<i-j<<" ";//由于本身字符串是从0开始计数的在i-j+1的基础上要减个1 
			j=ne[j];//接着找下一个匹配的位置 
			 //因为匹配成功后，p[j + 1]相当于是空字符，一定不匹配s[]中的任何字符，所以可以更新一次j。 
		}
	}
	return 0;
}