In computer science, a suffix automaton is the smallest partial deterministic finite automaton that recognizes the set of suffixes of a given string. (Wikipedia)
Given a string \$S\$ consisting of lowercase letters (a-z), construct the suffix automaton for it.
A suffix automaton is an array of states, 0-indexed or 1-indexed, depending on your implementation. The ID of a states is defined to be its location in the aforementioned array. The initial state \$t_0\$ is the state that corresponds to the empty string, and must be first in the array of states.
A state is defined as a sequence of 27 integers:
- The first integer is the state's suffix link, or the ID of the state that corresponds to the current state's longest suffix that occurs more times than the current state in \$S\$. In the case the this state is \$t_0\$, this value should be equal to a special value that is not a state ID.
- The second to 27th integer corresponds to the state's transition pointer, or the state ID that corresponds to this state's string + a letter, for characters
athroughzrespectively. In the case that such a state does not exist, this value should be equal to a special value that is not a state ID.
For further information on a suffix automaton and how to construct it, see the wikipedia page and the CP-algorithms page.
Input
The input string will be given in any acceptable format.
Output
Output the array of states in any acceptable format. Be sure to state the "special values that is not a state ID".
Example
For the string abbbcccaabbccabcabc, the suffix automaton's states should be structured similarly to this (blue edges = transition pointer, green dashed edges = suffix link):
For the string ddbadbdbddddbdbcabcdcaccabbbcbcbbadaccabbadcbdadcdcdbacbcadbcddcadcaaaacdbbbcaaadcaddcbaddbbcbbccdbc:
Scoring
This is code-golf, so shortest program (in bytes) wins.
Your code should run reasonably fast (in at most 10 seconds) for a string of length \$10^6\$. (If this requirement is too strict, I will relax the limit.)
