Cod sursă (job #416229)

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("bart.in");
ofstream g("bart.out");
int i,n,sol,k;
int prefix[500001];
char s[500001];
int main()
{
    f.getline(s+1,500001);
    n=strlen(s+1);
    k=0;
    for(i=2;i<=n;i++){
            while(k>0 && s[k+1]!=s[i]){
                    k=prefix[k];
            }
            if(s[k+1]==s[i]){
                    k++;
            }
            prefix[i]=k;
    }
    sol=n-prefix[n];
    for(i=1;i<=sol;i++){
            cout<<s[i];
    }
    return 0;
}