Cod sursă (job #94609)

#include <fstream>
#include<cstring>
#include<iostream>

using namespace std;

ifstream in("bart.in");
ofstream out("bart.out");

int a[500001], n;
char P[500001];

void preprocesare() {
    a[0] = 0;
    int k = 0;
    for (int q = 1; q < n; q++) {
      while ((k > 0) && (P[k] != P[q])) {
        k = a[k - 1];
      }
      if (P[k] == P[q]) {
        k++;
      }
      a[q] = k;
    }
  }

int main()
{
    int i, x;
    in >> P;
    n = strlen(P);
    preprocesare();
    for ( i = 0; i < n; i++ )
        if ( a[i] == 0 )
            x = i;
    for ( i = 0; i <= x; i++ )
        out << P[i];
    return 0;
}