Cod sursă (job #94612)

#include<cstdio>
#include<cstring>
using namespace std;

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

const int Nmax = 500001;
int pref[Nmax],d,m;
char P[Nmax];

void init() {
    pref[0] = 0;
    int k = 0;
    d=0;
    m=strlen(P);
    for (int q = 1; q < m; q++) {
      while ((k > 0) && (P[k] != P[q])) {
        k = pref[k - 1];
      }
      if (P[k] == P[q]) {
        k++;
      }
      pref[q] = k;
      if(k>d)
        d=k;
    }
}


int main (){
    fgets(P,Nmax,in);
    init();
    for(int q = 0 ; q < m - d - 1; q++)
        fprintf(out,"%c",P[q]);
    int q = m-d-1;
    while(!pref[q] && q < m){
        fprintf(out,"%c",P[q]);
        q++;
    }
    return 0;
}