UVA11452「Dancing the CheekyCheeky」
1. 题目
题目链接：UVA11452「Dancing the CheekyCheeky」 。
Description
The CheekyCheeky is a new song. They dance it in Mula, and also in Hong Kong. All the freekies dance it, and the geek all love it. And the CheekyCheeky is danced like this:
 The breikinbrokin.
 The meneito.
 The roboqueitor.
 The maiquelguolkin.
In this problem you have to learn to dance the CheekyCheeky. This dancing consists of $4$ basic steps (as listed above) that are arranged into a particular sequence. Then this sequence can be repeated an arbitrary number of times.
For example, if the sequence is 123
, then the CheekyCheeky is danced like this: 12312312312312...
. But if the sequence is 123124
, then the steps of the dancing are 123124123124123...
.
You are given some of the steps of a particular dancing. Those steps will contain between $2$ (inclusive) and $3$ (not inclusive) times the basic sequence. You have to continue the dancing.
For example, if the basic sequence is 123
, we can have the following possibilities:
Input  Output 

123123  12312312... 
1231231  23123123... 
12312312  31231231... 
Input
The first line of the input contains an integer indicating the number of test cases.
Each case contains some of the first steps of a dancing. It is a single line with a list of digits (1
, 2
, 3
or 4
) with no spaces between them. It will not have more than $2000$ steps. Remember that the case contains the basic sequence twice, and possibly has some more steps (but not thrice).
Output
For each test case, the output should contain the $8$ following steps of the dancing, followed by three dots ...
.
Sample Input
1 

Sample Output
1 

2. 题解
分析
由题意可知，每个输入字符串都包含且仅包含两个完整的重复序列，故利用前缀函数求出给定的字符串 $s$ 的最小周期 $k$ 即为重复序列的长度；根据 $s$ 末尾字符的下标 $n1$，故接下来的 8 字符串为 $s[n\%k .. n\%k+7]$ 。
代码
1 

本博客所有文章除特别声明外，均采用 CC BYSA 4.0 协议 ，转载请注明出处！