P3375 【模板】KMP字符串匹配

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e6+5;
 5 char s1[maxn], s2[maxn];
 6 int kmp[maxn];
 7 int main() {
 8     scanf("%s%s",s1,s2);
 9     kmp[0] = kmp[1] = 0;
10     int len1 = strlen(s1), len2 = strlen(s2), k = 0;
11     for (int i = 1; i < len2; i++) {
12         while (k && s2[i] != s2[k]) k = kmp[k];
13         kmp[i+1] = s2[i]==s2[k] ? ++k:0;
14     }
15     k = 0;
16     for (int i = 0; i < len1; i++) {
17         while (k && s1[i] != s2[k]) k = kmp[k];
18         k += s1[i]==s2[k] ? 1:0;
19         if (k == len2) printf("%d\n",i-len2+2);
20     }
21     printf("%d",kmp[1]);
22     for (int i = 2; i <= len2; i++) printf(" %d",kmp[i]);
23     printf("\n");
24     return 0;
25 }