Cod sursă (job #93851)

#include <stdio.h>

using namespace std;

const int N=500001;
char p[N];
int pref[N];

int main()
{
    FILE *in,*out;
    in=fopen("bart.in","r");
    out=fopen("bart.out","w");
    int i,j,m=0;

    fscanf(in,"%s",&p[0]);
    for(i=0;p[i];i++)
        m++;

    pref[0]=0;
    i=0;
    for(j=1;j<m;j++)
    {
        while(i>0 && p[i]!=p[j])
            i=pref[i-1];
        if(p[i]==p[j])
            i++;
        pref[j]=i;
    }
    for(i=0;i<m-pref[m-1];i++)
        fprintf(out,"%c",p[i]);
    return 0;
}