https://blog.csdn.net/nuoyanli/article/details/101618807

https://vjudge.net/problem/HDU-4468

https://www.zhihu.com/question/346899662

https://www.bilibili.com/video/av68668259/

非常漂亮的 KMP 題，模式串是在匹配文本串的過程中，生長出來的（自相似！）。

我們維護上一次模式串匹配到的位置，記做 o，如果在掃描當前文本串為止 i 的時候，發生匹配失敗，

不能用任何前綴表達，也就是 j = 0 的情況，我們就添加 T[o+1, i] 這一段的內容到模式串末尾。最後我們再補上 T[o+1, n] 這一段即可。

列印一下樣例的生長過程感覺一下！

abc a 1 abc ab 2 abc abc 3 Case 1: 3 aab a 1 aab a 1 aab ab 2 Case 2: 2 abcadabcabcad a 1 abcadabcabcad ab 2 abcadabcabcad abc 3 abcadabcabcad abc 1 abcadabcabcad abcad 5 abcadabcabcad abcad 1 abcadabcabcad abcad 2 abcadabcabcad abcad 3 abcadabcabcad abcad 4 abcadabcabcad abcad 2 abcadabcabcad abcad 3 abcadabcabcad abcad 4 abcadabcabcad abcad 5 Case 3: 5 aaabbbaaaabbbaa a 1 aaabbbaaaabbbaa a 1 aaabbbaaaabbbaa a 1 aaabbbaaaabbbaa ab 2 aaabbbaaaabbbaa abb 3 aaabbbaaaabbbaa abbb 4 aaabbbaaaabbbaa abbb 1 aaabbbaaaabbbaa abbb 1 aaabbbaaaabbbaa abbb 1 aaabbbaaaabbbaa abbb 1 aaabbbaaaabbbaa abbb 2 aaabbbaaaabbbaa abbb 3 aaabbbaaaabbbaa abbb 4 aaabbbaaaabbbaa abbb 1 aaabbbaaaabbbaa abbb 1 Case 4: 6 abcababcd a 1 abcababcd ab 2 abcababcd abc 3 abcababcd abc 1 abcababcd abc 2 abcababcd abc 1 abcababcd abc 2 abcababcd abc 3 abcababcd abcd 4 Case 5: 4

const int N = 1000009; char T[N], P[N]; int pi[N]; int n, m, o; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while (scanf("%s", T+1) != EOF) { n = strlen(T+1), m = 1, P[1] = T[1]; for (int i = 1, j = 0; i <= n; ++i) { while (j && T[i] != P[j+1]) j = pi[j]; if (T[i] == P[j+1]) ++j; if (!j){ for (int ii = o+1, jj = pi[m]; ii <= i; ++ii) { P[++m] = T[ii]; while (jj && P[m] != P[jj+1]) jj = pi[jj]; if (P[m] == P[jj+1]) ++jj; pi[m] = jj; } j = m; } if (j == m) o = i; //cout << T+1 << " " << P+1 << " " << j << endl; } memset(P+1, 0, sizeof(P[0])*m); printf("Case %d: %d\n", ++Case, m+n-o); //puts(""); } }