Cod sursă (job #294463)

#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 500002
using namespace std;
int m, p[Nmax], w[Nmax], maxl;
char s[Nmax];
void read()
{
    gets(s + 1);
    m = strlen(s + 1);
}
void prefix()
{
   int k = 0, q;
   p[1] = 0;
   for (q = 2; q <= m; ++ q)
   {
       while (k > 0 && s[k + 1] != s[q])
             k = p[k];
       if (s[k + 1] == s[q])
          ++ k;
       p[q] = k;
   }
}
void write()
{
    for (int i = 1; i <= m - p[m]; ++ i)
        printf("%c", s[i]);
}
int main()
{
    freopen("bart.in", "r", stdin);
    freopen("bart.out", "w", stdout);
    read();
    prefix();
    write();
    return 0;
}