Cod sursă (job #741681)

#include <bits/stdc++.h>

using namespace std;

string s;
vector <int> pi;

void kmp()
{
    for(int i = 1; i < s.size(); i ++)
    {
        int j = pi[i - 1];
        while(j  &&  s[i] != s[j])
            j = pi[j - 1];
        if(s[j] == s[i])
            pi[i] = j + 1;
        else
            pi[i] = 0;
    }
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("bart.in", "r", stdin);
    freopen("bart.out", "w", stdout);

    cin >> s;
    pi.resize(s.size(), 0);
    kmp();

    int len = s.size() - pi.back();
    for(int i = 0; i < len; i ++)
        cout << s[i];
    return 0;
}