953. How Many Different Pieces a String Contains
Given a string s, print how many DIFFERENT non-empty substrings it has. A
substring is a contiguous run of characters, and two occurrences of the same run
count once.
abc -> 6 a b c ab bc abc
aaa -> 3 a aa aaa
abab -> 7 a b ab ba aba bab abab
banana -> 15
## The straightforward version and where it stops
Put every substring in a hash set. For a string of length m there are
m (m+1) / 2 of them, which at m = 400 is 80200, and each one has to be
copied and hashed, costing up to 400 characters. That is about 16 million
characters of copying and hashing, plus the memory to hold every string.
## Every substring is a prefix of a suffix
That sentence is the whole problem. A substring starting at position i is a
prefix of the suffix that starts at position i. So the set of substrings of s
is exactly the set of prefixes of the suffixes of s.
And problem 939 already established that the number of distinct non-empty prefixes of a set of strings is the number of nodes in their trie, not counting the root, because a node is created the first time a prefix appears and never again.
So: insert all m suffixes into one trie and print the node count minus one.
nodes = 1
for i in 0 .. m-1:
node = root
for j in i .. m-1:
if child[node][s[j]] is absent: create it, nodes += 1
node = child[node][s[j]]
print nodes - 1
No string is ever built and no hashing happens; a repeated substring simply walks over nodes that already exist.
## Why no substring is counted twice and none is missed
Every node other than the root is reached by exactly one path from the root, and
that path spells exactly one string. That string is a prefix of some inserted
suffix, so it is a substring of s. Conversely every substring s[i..j] is
walked while inserting the suffix at i, so its node exists. The map between
non-root nodes and distinct substrings is a bijection, which is why counting
nodes IS counting substrings.
## Why the length limit is 400 and not 400000
The trie has at most 1 + m (m+1) / 2 nodes, so the node count grows with the
SQUARE of the length. At m = 400 that is at most 80201 nodes, and at 26 child
links of 8 bytes each, which is 208 bytes a node, the trie is at most
80201 * 208 = 16681808 bytes, about 16.7 MB. At m = 5000 the same formula gives
12502501 nodes and 2600520208 bytes, about 2.6 GB, which is why a suffix trie is
a teaching structure and a suffix automaton or suffix array is what real code
uses at scale.
## Boundaries
A string of one character answers 1. A string of m identical characters answers
m, since the only distinct substrings are the runs of each length. A string
with no repeated character at all answers the maximum m (m+1) / 2, which is
where the trie is a plain tree with no sharing whatsoever.
## Overflow
Nothing here overflows. The largest possible answer is 400 * 401 / 2 = 80200.
Constraints - `1 ≤ length of s ≤ 400` - `s` contains only lowercase English letters.
Input
The single line of input contains the string s.
Output
Print one integer: the number of different non-empty substrings of s, counting each distinct string once however many times it occurs.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.