= End-position equivalence
Two nonempty <substring>[substrings] have <end-position equivalence> when their sets of occurrence-ending positions in one fixed text are equal. This is the grouping used for states of a <suffix automaton>, with an additional initial state. In `ababa`, using one-based positions, `b` and `ab` both end at $\{2,4\}$, whereas `a` ends at $\{1,3,5\}$. Thus `b` and `ab` share a state despite their different lengths.<Suffix Automaton in the CP-Algorithms documentation>[End positions]{ref}
Equality of ending sets ensures that appending the same character gives equal new ending sets whenever the extension occurs. This makes character transitions well defined. Within a class the represented <string>[strings] are nested <string suffix>[suffixes], one at every length in an interval; <suffix links> connect that interval to the next shorter class.
Back to article page
