Cod sursă (job #741667)

#include <fstream>
#include <vector>

using namespace std;

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

int main()
{
    string s;
    cin >> s;

    vector < int > pi(s.size());
    pi[0] = 0;
    int k = 0, poz = 0;

    for(int i = 1; i < s.size(); i++)
    {
        while(k != 0 && s[k] != s[i])
            k = pi[k - 1];
        if(s[k] == s[i])
            k++;
        pi[i] = k;

        if(k == 0)
            poz = i + 1;
        else if(pi[i - 1] + 1 != k)
            poz = i;
    }
    for(int i = 0; i < poz; i++)
        cout << s[i];
    /*cout << '\n';

    for(int i = 0; i < s.size(); i++)
        cout << pi[i] << " ";
    cout << '\n';
    for(int i = 0; i < s.size(); i++)
    {
        cout << s[i] << " ";
        if(pi[i + 1] > 9)
            cout << " ";
    }*/
    return 0;
}