Cod sursă (job #600445)

#include <fstream>

#define NMAX 500005

using namespace std;

ifstream f("bart.in");
ofstream g("bart.out");

int last;
int pi[NMAX];
string str;

int main()
{
    f >> str;

    pi[0] = -1;
    for (int i = 1; i < str.size(); i++) {
        int k = pi[i - 1];

        while (k != -1 && str[i - 1] != str[k])  {
            k = pi[k];
        }

        pi[i] = k + 1;
    }

    for (int i = 0; i < str.size(); i++) {

        if (pi[i] == 1) {
            last = i - 1;
            continue;
        }

        if (pi[i] != pi[i - 1] + 1)
            last = i;
        //g << pi[i] << " ";
    }

    for (int i = 0; i < last; i++)
        g << str[i];

    return 0;
}