Cod sursă (job #741677)

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("bart.in");
ofstream fout ("bart.out");

int pi[4000005], nr;
string s;

int main()
{
    fin >> s;
    int n=s.size();
    int k=0;
    for (int i=1; i<s.size(); i++)
    {
        while (k!=0 && s[k]!=s[i])
            k=pi[k-1];
        if (s[k]==s[i])
            k++;
        pi[i]=k;
    }
    for (int i=0; i<=n-pi[n-1]-1; i++)
        fout << s[i];
    return 0;
}