【一本通】PowerStrings

- - C++ 代码
  - C语言代码

💐The Begin💐点点关注，收藏不迷路💐

求每个字符串的最短循环子串，输出循环次数。

输入

输入数据为多组数据，读取到"."字符时结束。每组数据仅有一行，长不会超过1000000个字符

输出

对于每组数据，输出一行，一个整数表示这个字符串的最短循环子串的循环次数。

样例输入

abcd
aaaa
ababab

样例输出

1
4
3

C++ 代码

#include <iostream>
#include <string>
using namespace std;
// 判断字符串s从索引start开始长度为len的子串是否是循环节
bool isCycle(const string& s, int start, int len) {
    int n = s.size();
    for (int i = start + len; i < n; i++) {
        if (s[i]!= s[i - len]) return false; // 如果对应位置字符不相等，不是循环节
    }
    return true;
}
int main() {
    string s;
    while (cin >> s && s!= “.”) { // 循环读取输入，直到遇到.结束
        int n = s.size();
        for (int i = 1; i <= n; i++) { // 尝试不同长度的子串作为可能的循环节
            if (n % i == 0) { // 如果当前长度能整除字符串长度
                if (isCycle(s, 0, i)) { // 判断是否是循环节
                    cout << n / i << endl; // 输出循环次数
                    break;
                }
            }
        }
    }
    return 0;
}

C语言代码

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
// 判断字符串s从索引start开始长度为len的子串是否是循环节
bool isCycle(const char* s, int start, int len) {
    int n = strlen(s);
    for (int i = start + len; i < n; i++) {
        if (s[i]!= s[i - len]) return false; // 如果对应位置字符不相等，不是循环节
    }
    return true;
}
int main() {
    char s[1000001];
    while (scanf(“%s”, s) == 1 && strcmp(s, “.”)!= 0) { // 循环读取输入，直到遇到.结束
        int n = strlen(s);
        for (int i = 1; i <= n; i++) { // 尝试不同长度的子串作为可能的循环节
            if (n % i == 0) { // 如果当前长度能整除字符串长度
                if (isCycle(s, 0, i)) { // 判断是否是循环节
                    printf(“%d\n”, n / i); // 输出循环次数
                    break;
                }
            }
        }
    }
    return 0;
}