Construction
Online: append characters. Each state has 'link' pointing to longest proper suffix state. States created + linked in O(1) amortized.
Advertisement
Node fields
len (longest string reaching state), link (suffix link), next (transitions).
Advertisement
Substring count
Each state represents equivalence class of substrings. Count = sum of (len(v) - len(link(v))) over all states.
Longest common substring
Build SAM of s1. Walk s2 through SAM, tracking longest match. O(N + M).