P3375 【模板】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