C. Хорошие подстрочки

#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;

const int N = 1e5 + 3;
const ull base = 13;

ull h[N], b[N];

ull get(int i, int j) {
    return (h[j] - ((i > 0) ? h[i - 1] * b[j - i + 1] : 0));
}

int main() {
    string s;
    cin >> s;
    int n = s.size();
    b[0] = 1;
    for (int i = 1; i <= n; ++i) {
        b[i] = b[i - 1] * base;
    }
    h[0] = s[0];
    for (int i = 1; i < n; ++i) {
        h[i] = (h[i - 1] * base + s[i]);
    }

    set<int> d;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            d.insert(i);
            d.insert(n / i);
        }
    }

    int ans = 0;
    for (int len: d) {
        ull temp = get(0, len - 1);
        bool ok = true;
        for (int i = len, j = 2 * len - 1; j < n; i += len, j += len) {
            if (get(i, j) != temp) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans++;
        }
    }

    cout << ans;
    return 0;
}