P5410 【模板】扩展 KMP

P5410 【模板】扩展 KMP

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e6+5;
 4 int q, nxt[maxn], extend[maxn];
 5 string a, b;
 6 void getnxt() {
 7     nxt[0] = b.size();
 8     int now = 0;
 9     while (b[now]==b[1+now] && now+1<b.size()) now++;
10     nxt[1] = now;
11     int p = 1;
12     for (int i = 2; i < b.size(); i++) {
13         if (i+nxt[i-p] < nxt[p]+p) nxt[i] = nxt[i-p];
14         else {
15             int now = nxt[p]+p-i;
16             now = max(now,0);
17             while (b[now]==b[i+now] && i+now<b.size()) now++;
18             nxt[i] = now;
19             p = i;
20         }
21     }
22 }
23 void exkmp() {
24     getnxt();
25     int now = 0;
26     while (a[now]==b[now] && now < min(a.size(),b.size())) now++;
27     extend[0] = now;
28     int p = 0;
29     for (int i = 1; i < a.size(); i++) {
30         if (i+nxt[i-p] < extend[p]+p) extend[i] = nxt[i-p];
31         else {
32             int now = extend[p]+p-i;
33             now = max(now,0);
34             while (b[now]==a[i+now] && now<b.size() && now+i<a.size()) now++;
35             extend[i] = now;
36             p = i;
37         }
38     }
39 }
40
41 int main() {
42     cin >> a >> b;
43     exkmp();
44     int len = b.size();
45     printf("%d",nxt[0]);
46     for (int i = 1; i < len; i++) printf(" %d",nxt[i]);
47     printf("\n");
48
49     len = a.size();
50     printf("%d",extend[0]);
51     for (int i = 1; i < len; i++) printf(" %d",extend[i]);
52     printf("\n");
53     return 0;
54 }