某島

… : "…アッカリ~ン . .. . " .. .
March 16, 2020

HDU 4468. SPY

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("");
    }
}