Cod sursă (job #741682)

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 5e6;
int p[N], ans[N];

int main () {

    string s;

    fin >> s;

    int n = s.size(), k = 0;
    for ( int i = 1; i < n; i++ ) {
        while ( k != 0 && s[k] != s[i] )
            k = p[k - 1];
        if ( s[k] == s[i] )
            k++;
        p[i] = k;
    }
    int length = n - p[n - 1];

    for ( int i = 0; i < length; i++ )
        fout << s[i];

    return 0;
}