Cod sursă (job #531917)

#include <fstream>

using namespace std;

int v[500005], n, lz;
string s, s2;

int main()
{
    ifstream cin("bart.in");
    ofstream cout("bart.out");
    cin>>s;
    //s=s+"#"+s2;
    n=s.length();
    //cout<<0;
    for(int i=1; i<n; ++i){
        int now=v[i-1];
        while(now>0&&s[now]!=s[i])
            now=v[now-1];
        if(s[now]==s[i])
            now++;
        v[i]=now;
        /*if(now==s2.length())
            cnt++;*/
        if(v[i]<v[i-1]||now==1)
            lz=i;
        //cout<<v[i];
    }
    //cout<<'\n';
    for(int i=0; i<lz; ++i)
        cout<<s[i];
    //cout<<cnt;
    return 0;
}