POJ 3581 - Sequence

Description: Given a string, split it into 3 consecutive subsequence, reverse each subsequence. To get the smallest result.

Solution:
Let S be the original string, S' be the reverse of S. The first subsequence mustbe the smallest sufix of S', since S[0]>S[1],S[2],...,S[n-1](It indicate that each sufix is different before end of the sufix).

Now the problem becomes to split a string into 2 consecutive substring, reverse each subsequence and get the smallest result. (Since the first subsequence is confirmed). Let s be the original string of S-(first subsequence), and s' be the reverse of s. The reverse of second and third subsequence can form the minimum notation of s' (illustrate the procedure and one can get it.).

Status:
First WA : Forgot to reverse the string when calculate the sufix array.

Second WA : The original solution is wrong. The original is, to get the second subsequence, just find another smallest sufix whose index is before the start of first sufix in S'. It's wrong because the end character of second subsequence is not unique, and it's next character in result string is the first character of S'. one case indicate this is "5 0 2 1 2 1 3", the wrong solution is 0 5 1 2 3 1 2, but the correct answer is 0 5 1 2 1 2 3. But this solution still indicate a inference in sufix array: After we find the smallest sufix and cut it away, the smaller sufix in orginal sufix array is still smaller in remainder (Use contradiction to prove it). Thus we don't need to get the sufix array in remainder again.

AC.