题目理解

题目要求我们找到一个字符串 s 的最大幂次 n，使得 s 可以表示为某个字符串 a 的 n 次方，即 s = a^n。这里的 a^n 表示字符串 a 重复 n 次拼接而成。例如：

• "abcd" 可以表示为 "abcd"^1，所以 n = 1。
• "aaaa" 可以表示为 "a"^4，所以 n = 4。
• "ababab" 可以表示为 "ab"^3，所以 n = 3。

解题思路

要解决这个问题，我们需要找到字符串 s 的最小循环节 a，然后计算 s 的长度除以 a 的长度，即可得到 n。具体步骤如下：

1. 计算字符串的Next数组：使用KMP算法中的Next数组（也称为部分匹配表）来帮助找到字符串的循环节。
2. 确定循环节长度：如果字符串 s 的长度 M 可以被 (M - Next[M]) 整除，那么 (M - Next[M]) 就是最小循环节的长度。否则，字符串 s 不能表示为某个字符串的多次重复，此时 n = 1。
3. 计算最大幂次 n：如果存在循环节，则 n = M / len，其中 len 是循环节的长度。

标程

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1 << 30;
const int maxn = 1e6+10;

char T[maxn];
int nxt[maxn], M;
void getNext(){
    ms(nxt, 0);
    int i = 0, j = -1;
    nxt[0] = -1;
    while(i < M){
        if(j == -1 || T[i] == T[j])
            nxt[++i] = ++j;
        else j = nxt[j];
    }
}
int main() {
    while(scanf("%s",T) && T[0]!='.'){
        M = strlen(T);
        getNext();
        int len = M-nxt[M];  //循环节t的长度

        if(nxt[M] == 0 || M%len != 0)
            cout << 1 << endl;
        else
            cout << M/len << endl;
    }
    return 0;
}

代码解析

1. 输入处理：使用 scanf 读取输入字符串，直到遇到 . 为止。
2. Next数组计算：getNext 函数计算KMP算法中的Next数组。Next数组的定义是：Next[i] 表示字符串的前 i 个字符组成的子串中，最长的相同前后缀的长度。
3. 循环节判断：
   • len = M - Next[M] 表示可能的循环节长度。
   • 如果 Next[M] == 0 或 M % len != 0，说明字符串没有循环节，n = 1。
   • 否则，n = M / len。

示例分析

1. 输入 "abcd"：
   • Next数组：[-1, 0, 0, 0, 0]。
   • len = 4 - 0 = 4。
   • 4 % 4 == 0，所以 n = 4 / 4 = 1。
2. 输入 "aaaa"：
   • Next数组：[-1, 0, 1, 2, 3]。
   • len = 4 - 3 = 1。
   • 4 % 1 == 0，所以 n = 4 / 1 = 4。
3. 输入 "ababab"：
   • Next数组：[-1, 0, 0, 1, 2, 3, 4]。
   • len = 6 - 4 = 2。
   • 6 % 2 == 0，所以 n = 6 / 2 = 3。

复杂度分析

• 时间复杂度：计算Next数组的时间复杂度是 O(M)，其中 M 是字符串的长度。由于每个测试用例都只处理一次，总的时间复杂度是线性的。
• 空间复杂度：需要额外的 O(M) 空间存储Next数组。

总结

通过KMP算法的Next数组，我们可以高效地找到字符串的最小循环节，从而计算出最大幂次 n。这种方法利用了字符串的自相似性，避免了暴力枚举，确保了算法的高效性。