UVA11452「Dancing the Cheeky-Cheeky」

1. 题目

题目链接：UVA11452「Dancing the Cheeky-Cheeky」 。

Description

The Cheeky-Cheeky 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 Cheeky-Cheeky is danced like this:

  1. The breikin-brokin.
  2. The meneito.
  3. The roboqueitor.
  4. The maiquel-guolkin.

In this problem you have to learn to dance the Cheeky-Cheeky. This dancing consists of 44 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 Cheeky-Cheeky 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 22 (inclusive) and 33 (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 20002000 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 88 following steps of the dancing, followed by three dots ....

Sample Input

1
2
3
4
5
6
7
6
123123
1231231
12312312
123124123124
12312412312412
12312412312412312

Sample Output

1
2
3
4
5
6
12312312...
23123123...
31231231...
12312412...
31241231...
41231241...

2. 题解

分析

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

// 前缀函数
struct PrefixFunction {
    #ifndef _PREFIXFUNCTION_
    #define ll int
    #define MAXN 20005
    #endif
    ll pi[MAXN];        // 前缀函数
    PrefixFunction() {}
    // 计算前缀函数
    void getPi(char *str, ll n) {
        pi[0] = 0;
        ll i = 1, j = pi[i-1];
        while(i < n) {
            if(str[i] == str[j]) {
                pi[i++] = j++ + 1;
            } else if(!j) {
                pi[i++] = j;
            } else {
                j = pi[j-1];
            }
        }
    }
};

int main()
{
    char steps[MAXN];
    PrefixFunction pf;
    ll t;
    scanf("%d", &t);
    for(ll i = 0; i < t; ++i) {
        scanf("%s", steps);
        ll n = strlen(steps);
        pf.getPi(steps, n);
        ll k = n - pf.pi[n-1];
        ll s = n%k;
        while(n < s+8) {
            steps[n] = steps[n%k];
            ++n;
        }
        steps[s+8] = '\0';
        printf("%s...\n", &steps[s]);
    }
    return 0;
}