Cod sursă (job #782869)

#include <fstream>
#include <cstring>

using namespace std;

const int N = 5e5;

char s[N+2];
int pref[N+1];

bool este_periodic(int lung)
{
    return (pref[lung] % (lung - pref[lung]) == 0);
}

int main()
{
    ifstream in("bart.in");
    ofstream out("bart.out");
    in >> (s + 1);
    int lung_p = pref[1] = 0, n = strlen(s + 1);
    for (int i = 2; i <= n; i++)
    {
        while (lung_p > 0 && s[i] != s[lung_p+1])
        {
            lung_p = pref[lung_p];
        }
        if (s[i] == s[lung_p+1])
        {
            lung_p++;
        }
        pref[i] = lung_p;
    }
    int lungime_sir_per = n;
    while (lungime_sir_per > 0 && !este_periodic(lungime_sir_per))
    {
        lungime_sir_per--;
    }
    int perioada = lungime_sir_per - pref[lungime_sir_per];
    s[perioada+1] = '\0';
    out << (s + 1) << "\n";
    in.close();
    out.close();
    return 0;
}