##### 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.

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