Cod sursă (job #525270)

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

using namespace std;

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

/*
    Indexam sirul de caractere de la 1
    Fie lungimea sirului de caractere Lung

    Ideea este urmatoarea :
    gasim lungimea celui mai lung sufix ( care e si prefix)
    care se termina pe ultima pozitie, fie aceasta X

    vom afisa de la 1 la Lung - X

    Astfel, prin scadere, vom ajunge in pozitia maxima unde
    niciun string nu se repeta


    pi[i] - sufixul ( care e si prefix ) care se termina pe pozitia i
*/

int pi[M];

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

    int k = 0;

    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;
}