Cod sursă (job #525269)

#include <iostream>
#include <fstream>

using namespace std;

ifstream f("bart.in");
ofstream g("bart.out");

const int maxn = 5e5+5;

string s;
int i, n;
int pr[maxn];

void prefix() {
    pr[1] = 0;
    int a = 0, i;
    for(i = 2; i <= n; i ++) {
        while(a > 0 && s[i] != s[a+1]) {
            a = pr[a];
        }
        if(s[i] == s[a + 1]) {
            ++ a;
        }
        pr[i] = a;
    }
}

int main()
{
    f >> s;
    n = s.size();
    s = " " + s;

    prefix();

    for(i = 1; i <= n - pr[n]; i ++) {
        g << s[i];
    }

    f.close(); g.close();
    return 0;
}