CSES - Finding Periods

Explanation

We can check if every prefix is valid using brute force. Due to harmonic series, this will only take $\mathcal{O}(N\log N)$ time if we can compare a substring to a prefix in $\mathcal{O}(1)$ time. This can be done using basic string hashing. When we precompute the hashes for prefixes of the string, we can get the hash for any substring using a variation of prefix sums but we multiply by the appropriate base.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll P = 69420;
const ll M = 1e9 + 9;

int main() {
	string s;
	cin >> s;