Cod sursă (job #676861)

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

int const NMAX = 5e5;
int kmp[1 + NMAX + 1];
char s[1 + NMAX + 1];

int main() {

  in >> s[0];
  int n = 1;
  for(int i = 1;in >> s[i];i++) {
    n++;
    int index = kmp[i - 1];
    while(index != 0 && s[index] != s[i]) {
      index = kmp[index - 1];
    }
    if(index == 0) {
      if(s[0] == s[i]) {
        kmp[i] = 1;
      }
    }else {
      kmp[i] = index + 1;
    }
    if(kmp[i] != i) {
      //cout << i - 1 << ' ' << i << ' ' << kmp[i - 1] << ' ' << kmp[i] << ": " << s[i - 1] << ' ' << s[i] << '\n';
    }
    //cout << kmp[i] << ' ';
  }
  //cout << n;
  int ans = n - 1 - kmp[n - 1];
  for(int i = 0;i <= ans;i++) {
    out << s[i];
  }
  return 0;
}