shubhamgoyal__'s blog

Suffix Array problem
By shubhamgoyal__, history, 8 years ago, In English

Can someone please explain the suffix array approach to this problem: http://www.spoj.com/problems/MINMOVE/

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • Append the input string at the back of itself.
  • Find the suffix array of the new string.
  • Traverse the suffix array from index 0 to s.size()/2 (Since we appended the same string at the back) and find the index with the minimum value.

  • This corresponds to the lexicographically smallest string and the rotations needed will just be the index value.

    The reason why it works is, if we take a window size of the original string and go through the new string, we get all rotations of the original string. So, finding the index with the lowest value gives the lexicographically smallest rotation.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I had a similar approach..but it fails for string like aaa..your answer would be 2..but answer is 0.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, you are correct. The answer would be 2 if we use the normal suffix array code. But, we can tweak the code to work in this case. The problem is strings that are completely prefix of another string will be taken to have a lower sorted index. Depending on how we have written the suffix array, it can be changed. For example, take the suffix array code from this link : Ideone (Code taken from codechef's suffix array tutorial page)

      When we look at line number 37, we have a condition check and a "-1" being inserted. This is to make sure, when sorting it comes before strings with the same prefix. So, if we replace this with a high number like "1e9" then while sorting, it will come after the strings of higher length with the same string as its prefix.

      By doing this, the same approach as stated above will work and now we will get the answer as 0 and not 2, according to the my understanding. Please let me know if I have missed out anything.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that, if you append the string to itself, every substring of length N will be a rotation.

Let's call the input string S and the new string T. You must find the lexicographically smallest substring of T with length N and break ties using indexes (the substring at position i represents i rotations).

To do this, you can construct the suffix array of T and look for the first suffix located before position N (remember that length(T) = 2N).

This will work for tests without ties, but what about strings like aaa or abcabc?

Let's say you found the suffix at position p (p ≤ N / 2). Now you must consider all suffixes that have the suffix located at p as a preffix, and the answer should be the leftmost suffix you find. This can be easily done using the Longest Common Preffix.

Hope this helps!

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But what is the need to break such ties? In the sorting potion of the suffix array creation algorithm, we can use a stable sort algorithm and that would ensure that two suffixes that are essentially the same will be sorted in the order of whichever has a lower starting position, thus emitting a minimum rotational move. Since radix sort is stable, no other rbreaking of ties would be required I guess.

    If I am missing something or overlooking some case, then please do point it out.

    cc: @bernett

    → Reply