如题，给出两个字符串 s1 和 s2，其中 s2 为 s1 的子串，求出 s2 在 s1? 中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组 next。
（如果你不知道这是什么意思也不要问，去百度搜 kmp算法 学习一下就知道了。）
第一行为一个字符串，即为 s1?。
第二行为一个字符串，即为 s2?。
若干行，每行包含一个整数，表示 s2在 s1? 中出现的位置
接下来 1 行，包括 ∣s2∣个整数，表示前缀数组 nexti的值。
KMP是通过一个f[]（fail）——或者叫next的‘自动机’来实现的。
把已经给出的串称为文本串，要在文本串中找的串称为模式串。
fail函数的含义是：在到这一位为止，前缀=后缀的最长长度是多少。
这里的=是指完全相同，比如ABCABC这样的，而不是对称，并且可以有重叠。
特别地，前两位（f[0],f[1]）为零。
比如串ABABACABABAC，它的fail应该为001230001230
构建自动机：
1 void getf() { 2 f[0] = f[1] = 0; 3 for(int i = 1; i < len2; i++) { 4 int j = f[i]; 5 while(j && p[i]!=p[j]) j = f[j]; 6 if(p[i] == p[j]) f[i+1] = j+1; 7 else f[i+1] = 0; 8 } 9 }
已知第i位的自动机f[i]，要求第i+1位的。
设j=f[i]。f[i]一定在i前面，f[i]已经求好了。
如果字符串的i+1和j+1位不同（s2[i]≠s2[j]），那么j不断地跳到自己的自动机f[j]，直到匹配上或j=0为止。
如果匹配上，f[i+1] = j+1；
否则如果还是s2[i]≠s2[j]，说明是j=0而不是匹配上了，那么f[j] = 0。
运行自动机：
1 void kmp() { 2 int j = 0; 3 for(int i = 0; i < len1; i++) { 4 while(j && s[i]!=p[j])j = f[j]; 5 if(s[i] == p[j])j++; 6 if(j == len2) { 7 printf("%d\n",1+i-len2+1); 8 j = f[j]; 9 } 10 } 11 }
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 #include<string> 7 const int maxn = 1e6+10; 8 int len1,len2,f[maxn]; 9 string s1,s2; 10 11 void find() { 12 f[0] = f[1] = 0; 13 for(int i = 1; i < len2; i++) { 14 int j = f[i]; 15 while(j && s2[i]!=s2[j]) j = f[j]; 16 if(s2[i] == s2[j]) f[i+1] = j+1; 17 else f[i+1] = 0; 18 } 19 } 20 21 void kmp() { 22 int j = 0; 23 for(int i = 0; i < len1; i++) { 24 while(j && s1[i]!=s2[j])j = f[j]; 25 if(s1[i] == s2[j])j++; 26 if(j == len2) { 27 printf("%d\n",1+i-len2+1); 28 j = f[j]; 29 } 30 } 31 } 32 33 int main() { 34 cin>>s1>>s2; 35 len1 = s1.length(); 36 len2 = s2.length(); 37 find(); 38 kmp(); 39 for(int i = 1; i <= len2; i++) 40 printf("%d ",f[i]); 41 return 0; 42 }
原文：https://www.cnblogs.com/very-beginning/p/12283569.html