Cod sursă (job #585148)

#include <iostream>
#include <fstream>
#include <string>

#define MX 500001

using namespace std;

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

int n, poz;
string s;
char pref[MX];

int main()
{
    fin>>s;
    n=s.size();
    s=' '+s;
    for(int i=2;i<=n;i++)
    {
        while(poz!=0 and s[i]!=s[poz+1])
            poz=pref[poz];
        if(s[i]==s[poz+1])
            poz++;
        pref[i]=poz;
    }
    for(int i=1;i<=n-pref[n];i++)
        fout<<s[i];

    return 0;
}