Delicious Dessert
Contest: Codeforces Round 846 (Div. 2)
Difficulty rating: 2400
Tags: binary search, dsu, hashing, math, number theory, string suffix structures

Today is an important day for chef Tonio — an auditor has arrived in his hometown of Morioh. He has also arrived at Tonio's restaurant and ordered dessert. Tonio has not been prepared for this turn of events.

As you know, dessert is a string of lowercase English letters. Tonio remembered the rule of desserts — a string $$$s$$$ of length $$$n$$$. Any dessert $$$t$$$ is delicious if the number of occurrences of $$$t$$$ in $$$s$$$ as a substring is divisible by the length of $$$t$$$.

Now Tonio wants to know the number of delicious substrings of $$$s$$$. If the substring occurs several times in the string $$$s$$$, then all occurrences must be taken into account.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of the rule $$$s$$$.

The second line contains the string $$$s$$$ of length $$$n$$$ — the rule. The rule consists only of lowercase English letters.

Output format:
In a single line print the number of delicious substrings of $$$s$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first sample, there are many delicious substrings. $$$7$$$ of them are substrings of length $$$1$$$ (because any number is divisible by $$$1$$$). Consider other delicious substrings:

- "ab" occurs in $$$s$$$ $$$2$$$ times, which is divisible by the length of the substring.
- "ba" also occurs $$$2$$$ times.

Therefore, the answer is $$$7 + 2 + 2 = 11$$$.

Note that the answer includes both occurrences of "ab" and "ba".

Example input:
7
abacaba

Example output:
11

Example input:
8
abaababa

Example output:
11

Editorial:
This problem has several solutions using different suffix structures. We'll cover two of them — one that uses a suffix array, and one that uses a suffix automaton.
First, let's build a suffix array $$$suf$$$ and an array of $$$lcp$$$ (greatest common prefixes) on string $$$s$$$. We fix some $$$k > 1$$$ and consider all substrings of the string $$$s$$$ of length $$$k$$$. Let's match $$$1$$$ to positions $$$i$$$ of array $$$lcp$$$, such that $$$lcp_i \geq k$$$, and $$$0$$$ to other positions. A unit at position $$$i$$$ means that substrings of length $$$k$$$ starting with $$$suf_i$$$ and $$$suf_{i + 1}$$$ are equal. Consider some block of length $$$len$$$ of units, then for $$$len + 1$$$ substrings of length $$$k$$$ the number of occurrences in $$$s$$$ is $$$len + 1$$$, then for the substrings in this block to be tasty, it is necessary that $$$ len + 1$$$ was divisible by $$$k$$$.
We will iterate over $$$k$$$ from $$$n$$$ to $$$2$$$ and support all block sizes. Then, when passing to a new $$$k$$$, it is necessary to support events - change $$$0$$$ to $$$1$$$, in such $$$i$$$ that $$$lcp_i = k$$$. To do this, you can support CHM. Then, when we know for each size - the number of blocks with this size, it suffices to consider all blocks of length $$$len$$$ such that $$$len + 1$$$ is a divisor of $$$k$$$. This can be done explicitly by iterating over $$$k$$$, $$$2 \cdot k$$$, ..., since this will work for the sum of the harmonic series.
For $$$k = 1$$$, obviously any substrings of length $$$1$$$ are fine, so you can just add $$$n$$$ to the answer.
The resulting asymptotics $$$O(n \cdot log(n))$$$
The solution with the suffix automaton is as follows: let's build the suffix automaton itself, now we calculate for each vertex of the suffix automaton the dynamics $$$dp_v$$$ — this is the number of paths from the vertex $$$v$$$ to the terminal vertices. This dynamics means the number of occurrences of the substring corresponding to this vertex in the entire string. Let's introduce the function $$$f(v)$$$ — the length of the longest substring leading to the vertex $$$v$$$. We know that all substrings of length from $$$l_v$$$ to $$$r_v$$$ lead to the vertex $$$v$$$ of the suffix automaton — each once. Where $$$r_v = f(v)$$$ and $$$l_v = f(suff_v) + 1$$$, where $$$suff_v$$$ is the suffix link of $$$v$$$. Why is it so? All substrings of the form $$$s[x:k], s[x+1:k], ..., s[y:k]$$$ lead to the vertex $$$v$$$ of the suffix automaton, and there is a suffix link $$$suff_v$$$ to which lead all substrings of the form $$$s[x + 1:k], s[y + 2:k], ..., s[t: k]$$$.
In order to solve the problem, let's go through the $$$v$$$ vertex and look at the number of occurrences of any substring that leads to the $$$v$$$ — $$$dp_v$$$ vertex, then fix $$$c$$$ - the number of such $$$l_v \le x \le r_v$$$, that $$$dp_v$$$ is evenly divisible by $$$x$$$. Therefore, $$$dp_v \cdot c$$$ must be added to the answer. All divisors can be stored in $$$O(n \cdot log(n))$$$ and each time find the number of such $$$x$$$ by binsearch.
Asymptotics $$$O(n \cdot log(n))$$$