Cod sursă (job #691530)

#include <bits/stdc++.h>

using namespace std;

ifstream fin  ("bart.in");
ofstream fout ("bart.out");

const int MAX_N = 500'000;
int n, len, kmp[MAX_N + 5];
string s;

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>s;
    n = (int)s.size();

    kmp[0] = len = 0;
    for(int i=1; i < n; i++){
        while(len > 0 && s[i] != s[len])
            len = kmp[len-1];
        len += (s[i] == s[len]);
        kmp[i] = len;
    }

    for(int i=0; i < n - kmp[n-1]; i++)
        fout<<s[i];
    return 0;
}