Cod sursă (job #698719)

#include <fstream>

using namespace std;

const int nmax=5e5;
int pi[nmax+3];

int main() {
        ifstream cin("bart.in");
        ofstream cout("bart.out");
        int k=0;
        string s;
        cin>>s;
        for(int i=1; i<s.size(); i++) {
                while(s[i]!=s[k]&&k!=0) {
                        k=pi[k];
                }
                if(s[i]==s[k])
                        k++;
                pi[i+1]=k;
        }
        cout<<s.substr(0,s.size()-pi[s.size()]);
        return 0;
}