Cod sursă (job #416242)

#include <bits/stdc++.h>

using namespace std;

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

char A[500001];
int M,pi[500001],L,rez;

void make_prefix(){
	int i, q = 0;
	for(i=2; i<=M; ++i)	{
		while(q>0 && A[q+1]!=A[i])
			q=pi[q];
		if(A[q+1]==A[i])
			++q;
		pi[i]=q;
	}
}

int main(){

    f.getline(A+1, 500001);
    M=strlen(A+1);
    make_prefix();
    int i=M;
    rez=i-pi[i];
    for(int i=1; i<=rez; ++i)
        g<<A[i];
    g<<'\n';
    return 0;
}