# 某島

… : "…アッカリ～ン . .. . " .. .
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/

```abc a 1
abc ab 2
abc abc 3
Case 1: 3

aab a 1
aab a 1
aab ab 2
Case 2: 2

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