http://codeforces.com/contest/126/problem/B

真心不好解释。。但这个代码是最简洁的。。

Forr(i, 2, len) if (f[i]) has[f[i]] = true;
if (has[i = f[i]] || has[i = f[i]]) ans = i;
/*62ms,5876KB*/

const int mx = 1000005;

char s[mx];
int f[mx];
bool has[mx];

int get_fail(char *p)
{
    f[1] = 0;
    int i, j;
    for (i = 1; p[i]; ++i)
    {
        j = f[i];
        while (j && p[i] != p[j]) j = f[j];
        f[i + 1] = (p[i] == p[j] ? j + 1 : 0);
    }
    return i;
}

int main()
{
    gets(s);
    int len = get_fail(s), i, ans = 0;
    Forr(i, 2, len) if (f[i]) has[f[i]] = true;
    if (has[i = f[i]] || has[i = f[i]]) ans = i;
    puts(ans ? s + (len - ans) : "Just a legend");
    return 0;
}

推广

如果要求有n个一样的子串呢?

Comments

comments powered by Disqus