E 悠悠碧波题解

听说数据水把暴力放过去了……还是写一写题解吧。
与CF126B一模一样的题。
KMP算法中，求了一个前缀函数： $\pi [i]$ 为前 $i$ 个字符组成的子串中、真前缀、真后缀相等的最大长度。
例如对于abcabcd

a, $\pi [1] = 0$ ，没有真前后缀。
ab, $\pi [2] = 0$
abc, $\pi [3] = 0$
abca, $\pi [4] = 1$
abcab, $\pi [5] = 2$
abcabc, $\pi [6] = 3$
abcabcd, $\pi [7] = 0$

那么对于给出的字符串求 $\pi$ 数组后，前后缀相等的最大长度即为 $\pi [len]$ 。
并且只要途中出现过 $\pi [i] = \pi [len],i \ne len$ ，就说明途中出现了一次与前后缀相同的字符串。

除此之外的一个坑点： $\pi [len]$ 可能大于所有 $\pi [i],i \ne len$ ，因此出现此种情况时缩短所取前后缀的长度： $\pi [len] = \pi [\pi [len]]$ ，直到存在 $\pi [i] >= \pi[len],i \ne len$ 。
如果缩短后 $\pi [len] = 0$ ，说明无解。
当然题目保证了有解了。
不懂前缀函数的可以去OI-Wiki看看。

#include <cstdio>
#include <cstring>
const int maxn = 1e5 + 100;
char s[maxn];
int maxx,len,pi[maxn];
int main()
{
    scanf("%s",s + 1);
    len = strlen(s + 1);
    for(int i = 2,k = 0;i<=len;++i)
    {
        while(k && s[i] != s[k + 1]) k = pi[k];
        if(s[i] == s[k + 1]) ++k;
        pi[i] = k;
        if(i != len && maxx < k) maxx = k;
    }
    while(pi[len] > maxx) pi[len] = pi[pi[len]];
    for(int i = 2;i<len;++i) if(pi[i] == pi[len])
    {
        for(int j = i - pi[i] + 1;j<=i;++j) putchar(s[j]);
        return 0;
    }
    return 0;
}