| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Language: Necklace Decomposition
Description ![]() 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. Input 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. Output For each scenario, output one line containing the necklace decomposition of the string. The necklaces should be written as '(' necklace ')'. Sample Input 5 0 0101 0001 0010 11101111011 Sample Output (0) (0101) (0001) (001)(0) (111)(01111)(011) Source |
[Submit] [Go Back] [Status] [Discuss]
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator