Cod sursă (job #676855)

#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];
char s[1 + NMAX + 1];

int main() {

  in >> s[0];
  int n = 1;
  for(int i = 1;in >> s[i];i++) {
    n++;
    in >> s[i];
    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;
    }
    //cout << kmp[i] << ' ';
  }
  int ans = 0;
  for(int i = n - 1;i >= 0;i--) {
    //cout << kmp[i];
    if(!(i == n - 1 || kmp[i] + 1 == kmp[i + 1]) || kmp[i] == 0) {
      //cout << i - 1 << ' ' << i << ' ' << i + 1 << ' ' << i + 2 << '\n';
      //cout << kmp[i - 1] << ' ' << kmp[i] << ' ' << kmp[i + 1] << ' ' << kmp[i + 2] << '\n';
      ans = i;
      break;
    }
  }
  for(int i = 0;i <= ans;i++) {
    out << s[i];
  }
  return 0;
}