KMP
https://blog.csdn.net/v_july_v/article/details/7041827
P3375 【模板】KMP字符串匹配
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 const int maxn = 1e6 + 10;
5 char s1[maxn], s2[maxn];
6 int l1, l2;
7 int nxt[maxn], f[maxn];
8
9 void work() {
10 for (int i = 2, j = 0; i <= l2; i++) {
11 while (j > 0 && s2[i] != s2[j + 1])
12 j = nxt[j];
13 if (s2[i] == s2[j + 1]) j++;
14 nxt[i] = j;
15 }
16 }
17
18 void kmp() {
19 for (int i = 1, j = 0; i <= l1; i++) {
20 while (j > 0 && (j == l2 || s1[i] != s2[j + 1]))
21 j = nxt[j];
22 if (s1[i] == s2[j + 1]) j++;
23 f[i] = j;
24 if (f[i] == l2) //s2在s1中的某一次出现
25 printf("%d
", i - l2 + 1);
26 }
27 }
28
29 int main() {
30 //freopen("in","r",stdin);
31 scanf("%s", s1 + 1);
32 scanf("%s", s2 + 1);
33 l1 = strlen(s1 + 1);
34 l2 = strlen(s2 + 1);
35 work();
36 kmp();
37 for (int i = 1; i <= l2; i++)
38 printf("%d ", nxt[i]);
39 return 0;
40 }
View Code