Cod sursă (job #232439)

#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=1;i<n;i++) {
        while(k>0&&sir[k]!=sir[i])
            k=ps[k];
        if(sir[k]==sir[i])
            k++;
        ps[i]=k;
    }
}

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