Cod sursă (job #92769)

#include <cstdio>

FILE*f=fopen("bart.in","r");
FILE*h=fopen("bart.out","w");

int t,n,pref[500005],k;

char b[500005],c;

int main(){
    fscanf(f,"%d\n",&t);
    fgets(b+1,sizeof(b),f);
    while( c!='\n' ){
        c=b[++n];
    }
    --n;
    pref[1]=0;
    for ( int i=2;i<=n;++i ){
        k=pref[i-1];
        while ( k>0&&b[k+1]!=b[i] )
            k=pref[k];
        if ( b[k+1]==b[i] )
            ++k;
        pref[i]=k;
    }
    int rez=-1;
    if ( pref[n]==0 )
        rez=n;
    for ( int i=n-1;i>=1&&rez==-1;--i ){
        if ( pref[i]!=pref[i+1]-1||pref[i]==0 )
            rez=i;
    }
    for ( int i=1;i<=rez;++i )
        fprintf(h,"%c",b[i]);
    return 0;
}