Cod sursă (job #741658)

#include <bits/stdc++.h>

using namespace std;

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

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

    string s; fin >> s;
    int p[ s.size() ];
    int n = s.size();
    p[0] = 0;
    int k = 0;
    for(int i = 1; i < n; i++){
        while(k != 0 && s[k] != s[i]){
            k = p[k - 1];
        }

        if(s[k] == s[i]) k++;
        p[i] = k;
    }

    //cout << "p : ";
    //for(int i = 0; i < n; i++) cout << p[i] << " ";
    //cout << endl;

    int lp = n - 1;
    while(p[lp] > 1) lp--;
    for(int i = 0; i < lp; i++) fout << s[i];
    fout << endl;

    if(lp == 0) fout << s << endl;

    return 0;
}