如题，给出两个字符串 s_1s1? 和 s_2s2?，其中 s_2s2? 为 s_1s1? 的子串，求出 s_2s2? 在 s_1s1? 中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组 next。
（如果你不知道这是什么意思也不要问，去百度搜 kmp算法 学习一下就知道了。）
第一行为一个字符串，即为 s_1s1?。
第二行为一个字符串，即为 s_2s2?。
若干行，每行包含一个整数，表示 s_2s2? 在 s_1s1? 中出现的位置
接下来 11 行，包括 |s2|∣s2∣ 个整数，表示前缀数组 next_inexti? 的值。
ABABABC ABA
1 3 0 0 1
时空限制：1000ms,128M
数据规模：
设 s_1s1? 长度为 NN，s_2s2? 长度为 MM。
对于 30\%30% 的数据：N\leq 15N≤15, M\leq 5M≤5。
对于 70\%70% 的数据：N\leq 10000N≤10000, M\leq 100M≤100。
对于 100\%100% 的数据：N\leq 1000000N≤1000000, M\leq 1000000M≤1000000。
太久没写题又打不开cf就洛谷试试水，，发现自己以前学懂了的东西忘得差不多了，，（看自己以前代码看得快睡着）
拿着以前不知道哪下的kuangbin板子照着列表写的，，第一题kmp发现自己没法盲打 于是水了一发 害，一上午就这么没了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 1e6+7; 5 char s1[N],s2[N]; 6 int nt[N]; 7 void getnext(char x[],int m){ 8 int i = 0,j;j = nt[0] = -1; 9 while(i < m){ 10 if(j==-1||x[i]==x[j]){nt[++i] = ++j;} 11 else j = nt[j]; 12 } 13 } 14 void kmp (char x[],int m,char y[],int n){ 15 int i = 0,j = 0,ans = 0; 16 getnext(x,m); 17 while(i < n){ 18 while(-1!=j && y[i]!=x[j]) j = nt[j]; 19 ++i;++j; 20 if(j >= m){ 21 printf("%d\n",i+1-m); 22 j = nt[j]; 23 } 24 } 25 return ; 26 } 27 28 int main() 29 { 30 scanf("%s%s",s1,s2); 31 int l1 = strlen(s1),l2 = strlen(s2); 32 getnext(s2,l2); 33 kmp(s2,l2,s1,l1); 34 for(int i = 1;i <= l2;++i){ 35 if(i!=1)printf(" "); 36 printf("%d",nt[i]); 37 }printf("\n"); 38 return 0; 39 }
原文：https://www.cnblogs.com/h404nofound/p/12179107.html