Cod sursă (job #376663)

#include <fstream>
#include <cstring>

using namespace std;

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

char ch[500002];
int pre[500002];

int l;

int main()
{
    in>>(ch+1);
    for(int i=2;i<=strlen(ch+1);i++)
    {
        while(l>0 && ch[l+1]!=ch[i])
            l=pre[l];
        if(ch[l+1]==ch[i])
            l++;
        pre[i]=l;
    }
    for(int i = 1;i<=strlen(ch+1)-pre[strlen(ch+1)];i++)
        out<<ch[i];
    return 0;
}