Cod sursă (job #525258)

#include <fstream>
#define M 500005

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 ; s[i] ; i++)
        if(pi[i] == maxk)
        {
            while(pi[i] > 1)
                i--;

            n = i;
            break;
        }

    for(int i = 1 ; i < n ; i++)
        cout << s[i];

    return 0;
}