Cod sursă (job #617591)

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

using namespace std;

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

const int MAXN = 500005;

int lcp[MAXN];

void getlcp( string w ) {
  int l = 0, r = 0;
  lcp[0] = 1;
  for ( int i = 1; i < w.length(); ++i ) {
    if ( i <= r ) {
      lcp[i] = min(lcp[i - l], r - i + 1);
    }
    while ( i + lcp[i] < w.length() && w[i + lcp[i]] == w[lcp[i]] ) ++lcp[i];
    if ( i + lcp[i] - 1 > r ) {
      l = i;
      r = i + lcp[i] - 1;
    }
  }
}

int main() {
  string s, res;
  int i = 0;

  fin >> s;
  getlcp(s);
  while ( i < s.length() && i + lcp[i] != s.length() ) {
    res.push_back(s[i]);
    ++i;
  }
  fout << res;
  fin.close();
  fout.close();
  return 0;
}