Cod sursă (job #416510)

#include <bits/stdc++.h>
using namespace std;
char a[500100];
int n,k,poz;
int p[500100];
int main()
{
    freopen("bart.in", "r", stdin);
    freopen("bart.out", "w", stdout);
    cin>>(a+1);
    n=strlen(a+1);
    int j=0;
    int i=2;
    p[1]=0;
    while(i<=n)
    {
        while(a[i]!=a[j+1]&&j>0) j=p[j];
        if(a[i]==a[j+1]) j++;
        p[i]=j;
        i++;
    }
    i=1;
    while(i<=n)
    {
        if(p[i]==0) poz=i;
        i++;
    }
    for(int i=1;i<=poz;i++) cout<<a[i];
    return 0;
}