Pro.ID21991 TitleShaking a String Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21991 AC0 Submit0 Ratio- 时间&空间限制描述The search engine company Elgoog has started to investigate alternative ways to index data that would allow for large amounts of data to be queried more cleverly than just about containing or not containing a substring. Working on this, the researchers discovered a transformation that has many interesting properties. They decided to call the transformation "shaking". Let's consider a string S of length n (2 ≤ n ≤ 1000000) consisting of lowercase Latin letters and the dollar sign ($). The latter is called a guard and has the code less than that of any of the letters. The guard appears only once in the string, in the last position. Then, for any integer k (1 ≤ k ≤ n-1, where k is a power of 2), we define the shaken form of S as the string T obtained as follows: 1) For every cyclic shift of S write out the triple (PRK, POS, LAST), where PRK is the first k characters of the shifted string, POS is the position (counting from zero) of the first letter of S in the shifted string, and LAST is the last character of the shifted string. 2) Sort the resulting triplets in ascending order , using the following rule to compare the triples: for any two triples C1 = (PRK1, POS1, LAST1) and C2 = (PRK2, POS2, LAST2) we will consider C1 < C2, if PRK1 is lexicographically less than PRK2 or , if they are equal, if POS1 < POS2. 3) After sorting the triples, write out the values of LASTi in that order. This sequence of letters is the shaken form T. Let's consider an example for k = 2:
The shaken form of a string usually has much simpler probabilistic structure than the original, which allows quite complicated information about S to be extracted from it using relatively simple algorithms. The researchers have accomplished that, but now they have decided it would be a waste to keep both the shaken T and the original S in the database. Using an automated theorem prover, they have learned that an efficient algorithm for extracting S from T must exist. However , they have been unable to derive the algorithm and have turned to you for help. 输入The first line contains the value k and the second line the shaken string T. 输出Description The search engine company Elgoog has started to investigate alternative ways to index data that would allow for large amounts of data to be queried more cleverly than just about containing or not containing a substring. Working on this, the researchers discovered a transformation that has many interesting properties. They decided to call the transformation "shaking". Let's consider a string S of length n (2 ≤ n ≤ 1000000) consisting of lowercase Latin letters and the dollar sign ($). The latter is called a guard and has the code less than that of any of the letters. The guard appears only once in the string, in the last position. Then, for any integer k (1 ≤ k ≤ n-1, where k is a power of 2), we define the shaken form of S as the string T obtained as follows: 1) For every cyclic shift of S write out the triple (PRK, POS, LAST), where PRK is the first k characters of the shifted string, POS is the position (counting from zero) of the first letter of S in the shifted string, and LAST is the last character of the shifted string. 2) Sort the resulting triplets in ascending order , using the following rule to compare the triples: for any two triples C1 = (PRK1, POS1, LAST1) and C2 = (PRK2, POS2, LAST2) we will consider C1 < C2, if PRK1 is lexicographically less than PRK2 or , if they are equal, if POS1 < POS2. 3) After sorting the triples, write out the values of LASTi in that order. This sequence of letters is the shaken form T. Let's consider an example for k = 2:
The shaken form of a string usually has much simpler probabilistic structure than the original, which allows quite complicated information about S to be extracted from it using relatively simple algorithms. The researchers have accomplished that, but now they have decided it would be a waste to keep both the shaken T and the original S in the database. Using an automated theorem prover, they have learned that an efficient algorithm for extracting S from T must exist. However , they have been unable to derive the algorithm and have turned to you for help. Input The first line contains the value k and the second line the shaken string T. Output The first and only line of the output should contain the original string S, followed by a newline. The guard symbol $ should be left out. Sample Input 2 Sample Output mississippi Source 样例输入2 样例输出mississippi 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 04:47 , Processed in 0.015664 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
