acwing831kmp字符串（模板题）
先暴力：
for i遍历s每一点当起点
for j 从i到i+n-1
如果s[ i ]!=p[ j ] break
但我们可以利用我们已经扫描过的s序列的信息看我们可以跳到p序列什么位置，使得p该位置之前和以扫描末尾段重合
板子如下：
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
const int M=100005;
char p[N],s[M];
int ne[N],n,m;
int main(int argc, char** argv) {
scanf("%d",&n); scanf("%s",p+1); scanf("%d",&m); scanf("%s",s+1);
//构造ne[]
for(int i=2,j=0;i<=n;i++){//i=1时不行，因为这样所有的ne就会等于自己本身，而我们要使不重的ne等于0（到头了）
while(j&&p[j+1]!=p[i]) j=ne[j];//要么到头了，要么j+1与i相等出来 ，到头了j=ne[j]=0
if(p[j+1]==p[i]) j++;//j+1（下一位）与i相等就更新下一位
ne[i]=j;//到头了j=0,不执行上if；如果是相等出来的就会执行上if，更新i的ne，即这段末尾与开头重合部分的末点
}
for(int i=1,j=0;i<=m;i++){
while(j&&p[j+1]!=s[i]) j=ne[j];//要么j到头了，要么满足下一个相等 ，每次ne都使j更小一点（相当于s序列前移）
if(p[j+1]==s[i]) j++;//如果下一个相等。j往下走
if(j==n){
printf("%d ",i-n);//程序s序列从1开始，题从0开始所以要长度-1，而长度是当前i-p串长+1
j=ne[j];//j到头了，理论上重新开始，但可以ne节省
}
}
return 0;
} 假设一个点可有两个ne，那么ne记录的最长的那个：
投递阿里巴巴控股集团等公司10个岗位 >
