Cod sursă (job #691523)

#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 500'000;
int n;
string s;

static inline int turn(const char &c){
    return (c - 'a' + 1);
}

const int MOD = 1'000'000'007;
const int B = 73;
int b[MAX_N + 5], prefix[MAX_N + 5];

static inline int lgput(int a, int b){
    int answer = 1;
    while(b != 0){
        if(b & 1)
            answer = (long long)answer * a % MOD;
        a = (long long)a * a % MOD;
        b >>= 1;
    }
    return answer;
}

static inline int query(int i, int j){
    int answer = prefix[j];
    if(i > 0){
        answer = answer - prefix[i-1] + MOD;
        if(answer >= MOD)
            answer -= MOD;
    }

    ///answer /= (B ^ i)
    answer = (long long)answer * lgput(b[i], MOD-2) % MOD;
    return answer;
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>s;
    n = (int)s.size();

    b[0] = 1;
    for(int i=1; i < n; i++)
        b[i] = (long long)b[i-1] * B % MOD;

    for(int i=0; i < n; i++)
        prefix[i] = (long long)b[i] * turn(s[i]) % MOD;

    for(int i=1; i < n; i++){
        prefix[i] += prefix[i-1];
        if(prefix[i] >= MOD)
            prefix[i] -= MOD;
    }

    bool posibil;
    int st, dr, prf;
    for(int len=1; len <= n; len++){
        prf = prefix[len-1];
        posibil = true;
        st = len;
        while(st < n){
            dr = st+len-1;
            if(dr >= n){
                dr = n-1;
                prf = prefix[dr-st];
            }

            if(query(st, dr) != prf){
                posibil = false;
                break;
            }

            st += len;
        }

        if(posibil){
            for(int i=0; i < len; i++)
                fout<<s[i];
            break;
        }
    }
    return 0;
}
/**
IWillNotWasteChalkIWillNotWasteChalkIWillNotWasteChalkIWillNotW
**/