Cod sursă (job #290686)

#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],m;
char P[Nmax];

void init() {
    pref[0] = 0;
    int k = 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;
    }
}


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