2014
01-05

# Necklace Decomposition

The set of cyclic rotations of a string are the strings obtained by embedding the string clockwise on a ring, with the first character following on the last, starting at any character position and moving clockwise on the ring until the character preceeding the starting character is reached. A string is a necklace if it is the lexicographically smallest among all its cyclic rotations. For instance, for the string 01011 the cyclic rotations are (10110,01101,11010,10101,01011), and furthermore 01011 is the smallest string and hence, a necklace.
Any string S can be written in a unique way as a concatenation S = T1T2 . . . Tk of necklaces Ti such that Ti+1 < Ti for all i = 1, . . . , k – 1, and TiTi+1 is not a necklace for any i = 1, . . . , k – 1. This representation is called the necklace decomposition of the string S, and your task is to find it.
The relation < on two strings is the lexicographical order and has the usual interpretation: A < B if A is a proper prefix of B or if A is equal to B in the first j – 1 positions but smaller in the jth position for some j. For instance, 001 < 0010 and 1101011 < 1101100

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario consists of one line containing a non-empty string of zeros and ones of length at most 100.

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario consists of one line containing a non-empty string of zeros and ones of length at most 100.

5
0
0101
0001
0010
11101111011

(0)
(0101)
(0001)
(001)(0)
(111)(01111)(011)

1. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

2. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）