Cod sursă (job #416159)

#include <bits/stdc++.h>

using namespace std;

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

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

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

int main(){

    f.getline(A, 500001);
    M=strlen(A);
	for(int i=M; i;--i)A[i]=A[i-1];
	A[0]=' ';

    make_prefix();
    int i=M;
    while(i>0){
        if(pi[i]==0){
            L=i;
            break;
        }
        --i;
    }
    for(int i=1; i<=L; ++i)
        g<<A[i];
    g<<'\n';
    return 0;
}