zcmu-1986

1986: 周期串plus

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 10  Solved: 7
[Submit][Status][Web Board]

Description

如果一个字符串可以由某个长度为k的字符串重复多次得到，我们说该串以k为周期。例如abcabcabcabc以3为周期（当然他也以6，12为周期）。输入一个长度不超过100000的串，输出他的最小周期。

Input

多组测试数据,每组仅一行为一个仅有大写字母组成的字符串。

Output

对于每组数据输出该字符串的最小周期。

Sample Input

HOHO

Sample Output

2

分析：第一眼看到100000以为这题是在卡时间，然后后面一直在优化代码，但是发现，其实在判断周期的时候有时

是重复的，这样可以节省了许多时间，但是这题100000主要只是吓吓你，做出来并没有卡在时间上。

这题没什么好讲的，直接进行求解。

代码

#include<iostream> #include<cstdio> #include<cstring> #define max 100000+10 using namespace std;int find(char a[]) {if(a==NULL)return -1;int size = strlen(a);int len = size / 2;bool flag = true;for(int i = 1;i <= len;++i){flag = true;for(int j = 0;j < i;++j){for(int k = i+j;k < size;k+=i){if(a[j] != a[k]){flag = false;break;}}if(flag == false){break;}}if(flag){return i;}}return size; }int main() {char s[max];while(cin>>s){cout<<find(s)<<endl;} }

总结

以上是生活随笔为你收集整理的zcmu-1986的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。