Cod sursă (job #94595)

#include <cstdio>
#include <cstring>

#define N 500000

char s[N];
int pi[N];

int main () {
    freopen ("bart.in", "r", stdin);
    freopen ("bart.out", "w", stdout);

    int m;
    gets (s);
    m = strlen (s);

    pi[0] = 0;
    int k = 0;
    for (int q = 1; q <= m - 1; q++) {
        while (k && s[k] != s[q]) {
            k = pi[k - 1];
        }

        if (s[k] == s[q]) {
            k++;
        }

        pi[q] = k;
    }

    int n = m - pi[m - 1];
    for (int i = 0; i < n; i++) {
        printf ("%c", s[i]);
    }
    printf ("\n");

    return 0;
}