【UVA – 455】Periodic Strings【紫书】

【UVA – 455】Periodic Strings【紫书】

问题链接:

udebug数据链接:

核心思路:

记最小周期子串为\(V\),开始时,将一行输入的第一个字符加入这个序列\(V\)中,之后要做的就是:循环判断当前\(V\)是否是周期子串,如果是,则直接结束判断,输出序列\(V\)的长度;如果不是,将输入数据的下一个字符加入序列\(V\)中,重复上述步骤。

更多细节:首先,实现中的\(V\)不需要另外开数组存储,假设我们已经将一行输入放到data数组中,根据上边的描述,data[0]先算作序列\(V\)中的唯一元素,接下来从data[1]开始,此时data[0]是属于上述序列\(V\)的,需要判断从data[1]开始到最后的字符是否一直是\(V\)的多次重复,也就是说,对于\(i = 1\)【这个是V的长度】及\(j = 1 … len – 1\),判断data[j % i]是否相等于data[j],如果存在不等,则说明当前序列\(V\)不是最小周期子串,则将data[1]也算入\(V\),从实现上,可以把\(i++\)变成2,表示序列\(V\)长度为2,需要从data[2]开始到data[j – 1]判断是否满足data[j % i]恒等于data[j]…持续上述过程,最终可以找到解。

备注:

三点需要注意:

1.形如ababbab这样的字符串,如果忽略检查最后一个子串是否是完整的最小周期串,则会得到错误答案5【即ababb,因为ababb的前两个字符与最后一个子串ab能够匹配】。一种检查方案是,对于长度为\(len\)的字符串,只有对长度为\(l\)且满足\(len % l = 0\)的子串可能成为最小周期串。

2.如果使用fgets()函数或者类似的会保留换行符的读取函数,需要先去掉最后的换行符,同时,由于输入字符串最多有80个字符,考虑到这个换行符,以及字符串结束标识,字符串数组至少要开82的大小。

3.本题输入输出格式要求的空行需要注意。

Solution:

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 82;
char data[LIM];

int main(void) {
    int t;
    scanf("%d", &t);
    for (int k = 0; k < t && fgets(data, LIM, stdin);) {
        if (data[0] == '\n') continue;
        if (k) putchar('\n');
        int len = strlen(data) - 1;
        data[len] = 0;         // remove the last '\n'
        k++;
        int i, j;
        for (i = 0; data[i]; i++) {
            for (j = i; j && data[j]; j++) {    // 对于i等于0时,应当直接跳过内层循环
                if (len % i) break;
                if (data[j % i] != data[j]) break;
            }
            if (!data[j]) break;
        }
        printf("%d\n", i);
    }
    return 0;
}