Cod sursă (job #600446)

#include <fstream>
#include <climits>

#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;
    str = str + str[0];

    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() - pi[str.size() - 1] - 1; i++)
        g << str[i];

    return 0;
}