UVa 146

From Algorithmist
Jump to navigation Jump to search

146 - ID codes[edit]

Summary[edit]

The pattern of the succesor of a given string is explored and found. The algorithm follows from it.

Explanation[edit]

Given a string S, in order to find its successor, we need to find out the rightmost character y such that y is "less than" some character x in R(y), where R(y) denotes the substring of S that is to the right of y. Let's assume that x is the rightmost character in R(y) that is "bigger than" y. So we have the following situation:

+-----+---+----+---+----+
| ... | y | WL | x | WR |
+-----+---+----+---+----+ ,

where WL is the substring of S that is sandwiched between y and x, and WR is the substring of S that is to the right of x. Both WL and WR could be empty.

Since y is the rightmost character in S that is "less than" some character in substring WL+x+WR, WL+x+WR is non-increasing. Also, x is the rightmost character in R(y) that is "bigger than" y. So the successor of S must have x in y's position and y,WL,WR to the right of x. Moreover, the string consisting of y,WL,WR has to be in non-decreasing order. So, the successor of S is:

+-----+---+----+---+----+
| ... | x |~WR | y |~WL |
+-----+---+----+---+----+ ,

where ~WR denotes the reversed WR and ~WL the resersed WL. The string ~WR+y+~WL is in non-decreasing order because: (1) ~WR is in non-decreasing order because WR is non-increasing. So is ~WL; (2) y<~WL (or WL) because y<x and x<=WL; (3) y>=~WR (or WR) because x is the rightmost character in R(y) of S that is bigger than y.

Solution[edit]