About Suffix Automaton

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.