2
\$\begingroup\$

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 a through z respectively. 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):

SAM 1

For the string ddbadbdbddddbdbcabcdcaccabbbcbcbbadaccabbadcbdadcdcdbacbcadbcddcadcaaaacdbbbcaaadcaddcbaddbbcbbccdbc:

SAM 2

Scoring

This is , 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.)

| improve this question | |
\$\endgroup\$
  • \$\begingroup\$ I think the time requirement is too strict. It completely rules out everything except the O(nlogk) algorithm, and in some languages even the O(nlogk) might not run in 2 seconds, rendering some languages completely useless for this challenge. I also think you should set a less ambiguous definition of "your program's return should represent this", because it might lead to conflict regarding what constitutes a representation of a graph and what doesn't. \$\endgroup\$ – Windmill Cookies Apr 16 at 12:51
  • 1
    \$\begingroup\$ @WindmillCookies Concerning time limit: You can construct it in O(n). (My C++ code runs in under 1 second.) Concerning representation: I clearly stated the representation as an array of states. (Ok, I reworded it a bit) \$\endgroup\$ – Baaing Cow Apr 16 at 13:00
  • 1
    \$\begingroup\$ This is an awesome question. If only I had time to answer it. There are tags restricted-time and restricted-complexity. You may want one of those. \$\endgroup\$ – Anush Apr 16 at 13:09
  • 1
    \$\begingroup\$ @BaaingCow OK, but still some languages are slow and can't run 10^6 operations in 2 seconds. With that tight of a time limit, everyone will send the port of the same answer and it will not be very interesting. \$\endgroup\$ – Windmill Cookies Apr 16 at 13:10
  • \$\begingroup\$ @WindmillCookies I am not sure this matters does it? The task is sufficiently complicated that answers are likely to be different in detail even if similar in overall approach. We have lots of trivial code-golf questions on this site and no one complains that all the answers are implementing the same algorithm. Also, see codegolf.stackexchange.com/questions/193011/… . That's a perfectly good challenge despite the existence of very slow languages. \$\endgroup\$ – Anush Apr 16 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.