Cod sursă (job #617608)

#include <bits/stdc++.h>

using namespace std;
int const N = 5e5 + 3;
ifstream f ("bart.in");
ofstream g ("bart.out");
char s [N];
int z [N];
int main()
{
    f >> s;
    int n = strlen (s);
    int l , r;
    l = r = 0;
    z [0] = 0;
    for(int i = 1 ; i < n ; ++ i){
        if (i <= r)
            z [i] = min (z [i - l] , r - i + 1);
        while (i + z [i] < n && s [z [i]] == s [i + z [i]])
            ++ z [i];
        if (i + z [i] - 1 > r){
            r = i + z [i] - 1;
            l = i;
        }
    }
    int ans (n);
    for(int i = 0 ; i < n  ; ++ i){
        if (i + z [i] == n)
            ans = min (ans , i);
    }
    s [ans] = '\0';
    g << s;
    return 0;
}