1841. How Many Different Pieces, at Full Size
Print how many DIFFERENT non-empty contiguous pieces s has. Two occurrences of
the same piece count once.
banana -> 15 out of 21 by position
aaaa -> 4 out of 10
abc -> 6 every piece is different
abab -> 7
mississippi -> 53
Problem 953 asks exactly this at |s| <= 400, where a trie of the suffixes has
at most 80200 nodes and is the intended answer. Here |s| reaches 200000, the
same trie needs up to 2.00001 * 10^10 nodes, and the ANSWER itself no longer
fits in a 32 bit integer.
## What most people try first
Put every piece in a set. There are n(n+1)/2 of them, about 2 * 10^10 at
n = 200000, each costing up to n characters to build and hash. The trie of
suffixes removes the copying and keeps the node count, which is the same
2 * 10^10. The method below is O(n log n), about 3.6 * 10^6 steps, with
O(n) memory.
## Every piece is a prefix of a suffix, counted once
A piece starting at i is a prefix of the suffix starting at i, so the pieces
of s are exactly the prefixes of its suffixes. Counting them with repetition
gives n(n+1)/2. The repetitions are precisely the prefixes shared by two
suffixes that are ADJACENT in sorted order, and the agreement array of problem
1838 says how many each pair shares.
answer = n(n+1)/2 - (sum of the agreement array)
## Why subtracting only the neighbours is enough
Sort the suffixes. Walk them in order and ask how many NEW prefixes each one
contributes. The suffix at sorted position t has length n - sa[t] prefixes,
and the ones already seen are exactly those it shares with the suffix before it,
because sorted order means the previous suffix agrees with it at least as much
as any earlier one does.
So each suffix contributes (n - sa[t]) - lcp[t-1] new pieces, and summing that
over all t gives n(n+1)/2 minus the sum of the agreements. Nothing is
subtracted twice, because each suffix is compared only with its immediate
predecessor.
## Overflow
n(n+1)/2 at n = 200000 is 20000100000, about 2 * 10^10, which is nine
times the 2147483647 a signed 32 bit integer holds. So the total, and the
subtraction, must both be done in 64 bit arithmetic. The agreement values
themselves are at most 2 * 10^5 and fit in 32 bits, but their SUM does not.
## Cost
O(n log n) time, 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` - occurrences of a piece may overlap, and two occurrences of the same piece count once, so a single total is wanted
Input
A single line containing the string s, of lowercase English letters.
Output
Print one integer on its own line: how many distinct non-empty contiguous pieces the string has, counting two occurrences of the same piece once.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.