Cod sursă (job #525263)

#include <fstream>
#define M 500005
#include <cstring>

using namespace std;

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

int pi[M];

int main()
{
    string s;
    cin >> s;
    s = " " + s;

    int k = 0, n, maxk = -1;

    for(int i = 2 ; s[i] ; i++)
    {
        while(s[i] != s[k + 1] && k)
            k = pi[k];

        if(s[i] == s[k + 1])
            k++;

        pi[i] = k;
        maxk = max(maxk, k);
    }

    for(int i = 1 ; i < s.size() - pi[s.size() - 1] ; i++)
        cout << s[i];

    return 0;
}