Cod sursă (job #232451)

#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

char sir[500005];
int n,ps[500005];

void findPattern() {
    int k=0;
    for(int i=2;i<=n;++i) {
        while(k>0&&sir[k+1]!=sir[i])
            k=ps[k];
        if(sir[k+1]==sir[i])
            ++k;
        ps[i]=k;
    }
}

int main()
{
    ifstream fin("bart.in");
    ofstream fout("bart.out");
    fin.get(sir+1,500005);
    n=strlen(sir+1);
    findPattern();
    for(int i=1;i<=n-ps[n];++i)
        fout<<sir[i];
    return 0;
}