= Suffix link
In a <suffix automaton>, a <suffix link> from state $v$ leads to the state containing the longest <string suffix>[suffix] of its longest represented <string> that lies in a different <end-position equivalence> class. If $L(v)$ is the maximum represented length, state $v$ represents one <string> at each length from $L(\operatorname{link}(v))+1$ through $L(v)$. Following links strictly decreases length and eventually reaches the initial state.<Suffix Automaton in the CP-Algorithms documentation>[Suffix links and Recap]{ref}
For `ababa`, the state representing `ababa` also represents `baba`; its link leads to the state containing `aba`. This skips a <string suffix>[suffix] already in the current class. The links form a <rooted tree> useful for propagating occurrence counts from longer matches to shorter <string suffix>[suffixes].
Back to article page
