Cod sursă (job #617587)

#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;
const int NMAX = 500000;

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

char s[NMAX];
int z[NMAX];

void initZ(char s[], int z[]);

int main()
{
    int i, pos, n;
    fin >> s;
    initZ(s, z);
    n = strlen(s);
    pos = 0;
    while (pos + z[pos] < n)
        pos++;
    for (i = 0; i < pos; i++)
        fout << s[i];

    return 0;
}

void initZ(char s[], int z[])
{
    int len = strlen(s), l = 0, r = 0;
    z[0] = 0;
    for (int i = 1; i < len; i++)
    {
        if (r <= i)
            z[i] = 0;
        else
            z[i] = min(z[i - l], r - i + 1);
        while (i + z[i] < len && s[z[i]] == s[i + z[i]])
            z[i]++;
        if (r < i + z[i] - 1)
        {
            l = i;
            r = i + z[i] - 1;
        }
    }
}