如果一个字符串可以由某个长度为k的字符串重复多次得到,我们说该串以k为周期。例如,abcabcabcabc以3为周期(注意,它也以6和12为周期)。输入一个长度不超过80的串,输出它的最小周期。使用C语言代码实现
时间: 2024-12-19 22:26:06 浏览: 8
求周期串周期和子内容.cpp
在C语言中,我们可以使用滑动窗口或者滚动数组的方法来寻找一个字符串的最小周期。以下是基于滚动数组的简单实现:
```c
#include <stdio.h>
#include <string.h>
int findMinPeriod(char str[], int n) {
if (n <= 1)
return n;
// 创建一个长度为n的布尔数组,表示每个位置是否属于当前子串的一部分
int length[n];
for (int i = 0; i < n; ++i)
length[i] = (str[i] == str[0]);
// 初始化最小周期为n,然后开始滚动数组
int min_period = n;
for (int j = 1; j < n; ++j) {
// 检查从当前位置开始的子串是否等于第一个字符的子串
bool match = true;
for (int i = 0; i + j < n; ++i) {
match &= (str[i] == str[i + j]);
length[i + j] = match;
}
// 如果匹配成功并且新周期更小,更新最小周期
if (match && j < min_period)
min_period = j;
}
return min_period;
}
int main() {
char str[] = "abcabcabcabc";
int n = strlen(str);
printf("The minimum period is %d\n", findMinPeriod(str, n));
return 0;
}
```
这个函数首先检查原始字符串的第一个字符是否构成一个完整的周期,如果是,则返回1。然后,它从第二个字符开始循环,每次移动一位,检查新的子串是否等于之前的子串,如果匹配并且新周期比已知的最小周期短,就更新最小周期。最后,返回找到的最小周期。
阅读全文