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

# | User | Rating |
---|---|---|

1 | tourist | 3771 |

2 | jiangly | 3688 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | djq_cpp | 3486 |

6 | MiracleFaFa | 3466 |

7 | ksun48 | 3452 |

8 | Radewoosh | 3406 |

9 | greenheadstrange | 3393 |

10 | xtqqwq | 3382 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 183 |

2 | awoo | 181 |

3 | YouKn0wWho | 177 |

4 | Um_nik | 175 |

5 | dario2994 | 172 |

6 | Monogon | 171 |

7 | adamant | 168 |

8 | maroonrk | 167 |

9 | antontrygubO_o | 166 |

10 | errorgorn | 164 |

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

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2022 03:57:09 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

This corresponds to the lexicographically smallest string and the rotations needed will just be the

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

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.

Thanks for the great explanation!

Note that, if you append the string to itself, every substring of length

Nwill be a rotation.Let's call the input string

Sand the new stringT. You must find the lexicographically smallest substring ofTwith lengthNand break ties using indexes (the substring at positionirepresentsirotations).To do this, you can construct the suffix array of

Tand look for the first suffix located before positionN(remember thatlength(T) = 2N).This will work for tests without ties, but what about strings like

aaaorabcabc?Let's say you found the suffix at position

p(p≤N/ 2). Now you must consider all suffixes that have the suffix located atpas 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!