Some Properties
- Each state in the SAM corresponds an equivalent class of substrings of $s$ which appear in the same set of positions.
- For some state $v$, $len(v) – minlen(v) + 1$ is the number of distinct substring in the corresponding class.
About String Matching
To check if $t$ occurs in $s$, we can keep matching $t$ on the SAM of $s$, go to the next state if the current character is matched, or get through suffix link otherwise.
If we want to know how much a string $t$ can be matched for each state in the SAM of $s$, we can first keep matching it and record whenever the character is matched, and then we can propagate the value through the links.
About Paths in the DAG
Fact: Every distinct path from the root is a distinct substring.
Following from this fact, we can use DP to calculate lots of things, such as number of distinct substrings, sum of distinct integers.
Example: sum of dictinct integers, Morse Code
About Suffix-Link Tree
The suffix links forms a tree in which you can propagate information upwards, like the first/last ocurring positions, number of characters matched in a suffix, etc.
Example: propagation of available indices
Related Problems
Sliding Windows for String Matching: HDU 6583
Analysis in the blog for the original contest.