1819. Counting Every Place a Prefix Begins
Count the pairs (i, L) with L >= 1 such that the L characters of s starting
at position i are exactly the first L characters of s. Print that count.
Occurrences may OVERLAP each other and may overlap the prefix they copy, and a single total is wanted.
aaaa -> 10 4 + 3 + 2 + 1
abcabc -> 9 6 from position 0 and 3 from position 3
abcdef -> 6 only the whole string counts
aabaabaab -> 21
Read aaaa. Position 0 supports L = 1, 2, 3, 4. Position 1 supports
L = 1, 2, 3, and the L = 3 copy at position 1 overlaps the one at position 0
in two characters. All of them count.
## What most people try first
For every i, walk forward while the characters agree with the prefix, adding
one to the total per step. That is O(n^2): on 200000 identical characters it
is about 2 * 10^10 steps, and the answer itself is 2 * 10^10. The method
below does about 4 * 10^5 steps and still reports that number.
## The Z array already counts them
At position i, the values of L that work are exactly 1, 2, ..., z[i],
because agreement is prefix-closed: if the first L characters from i match
the prefix, so do the first L-1. So position i contributes z[i] pairs, and
answer = z[0] + z[1] + ... + z[n-1]
z[0] is n, which correctly counts every prefix matching itself at position 0.
## Why this is a counting problem and not an enumeration problem
The answer can be as large as n(n+1)/2, which at n = 200000 is
2.00001 * 10^10. Any method that touches each pair individually is doomed
before it starts, however cleverly it is pruned. The Z array turns a count of
pairs into a sum of n numbers, which is the same move problem 1808 makes with
the prefix function.
## Overflow
The total reaches 2.00001 * 10^10 at the limit, which is about nine times the
2147483647 a signed 32 bit integer holds, so the accumulator must be 64 bit.
The individual Z values are at most 2 * 10^5 and fit in 32 bits with enormous
room; widening them too is harmless but unnecessary.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - the answer can reach `n(n+1)/2`, which is about `2 * 10^10`
Input
A single line containing the string s, of lowercase English letters.
Output
Print one integer on its own line: the number of pairs of a starting position and a length such that the piece beginning there equals the prefix of s of that length.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.