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