企业视频网站模板,点样做网站,北京seo技术,遵义网站建设oadmin原题链接#xff1a;https://uva.onlinejudge.org/index.php?optioncom_onlinejudgeItemid8category830pageshow_problemproblem396 题意#xff1a; 如果一个字符串可以由某个长度为k的字符串重复多次得到#xff0c;则称该串以k为周期。例 …原题链接https://uva.onlinejudge.org/index.php?optioncom_onlinejudgeItemid8category830pageshow_problemproblem396 题意 如果一个字符串可以由某个长度为k的字符串重复多次得到则称该串以k为周期。例 如abcabcabcabc以3为周期注意它也以6和12为周期。 输入一个长度不超过80的字符串输出其最小周期。 解题思路过程 首先我想到的是用队列 把待测串s[]的首字符s[0]入队从第二个字符s[1]开始和队首元素对比 ifs[i]c.pop())(c为队列队首出队sum else c.push(s[i]) 一直到队列为空or所有元素都遍历过一遍为止。 最后如果sum0 || 串的长度与sum取模0 就说明它的最短周期是它本身 1 #include iostream2 #includestring3 #includequeue4 using namespace std;5 int main(){6 int T;7 cinT;8 while(T){9 string a;
10 cina;
11 int lena.length();
12 int lenalen;
13 len--;
14 queuecharc;
15 c.push(a[0]);
16 int i1,sum0;
17 while(!c.empty()len){
18 char tempc.front();
19 if(tempa[i]){
20 c.pop();sum;
21 }
22 else c.push(a[i]);
23 i;len--;
24 }
25 // if(sum1)sumlena;
26 if(sum0)sumlena;
27 else if((lena%sum)!0)sumlena;
28 coutsumendl;
29 T--;
30 }
31 return 0;
32 } 后来测试才发现这算法有个致命的bug “算法盲点”amanamanamanaman按此串所模式最小周期应该是4但因为使用队列的缘故无法实现出现队列为空的情况顾此路不通。。。 经过重新观察数据规模发现和题意发现通过枚举完成此题。 1 #include iostream2 #includestring3 #includequeue4 using namespace std;5 int main(){6 int T;7 cinT;8 while(T){9 string a;
10 cina;
11 int ok1;
12 int lena.length();
13 for(int i1;ilen;i){
14 if(len%i0){
15 ok1;
16 for(int ji;jlen;j){
17 if(a[j]!a[j%i]){
18 ok0;
19 break;
20 }
21 }
22 }
23 if(ok){coutiendl;break;}
24 }
25 T--;
26 }
27 return 0;
28 } 首先从1开始枚举子串长度如果待测串%子串长度0就可以接着去对照待测串中的元素最终找出待测串的最小周期转载于:https://www.cnblogs.com/yifeianyi/p/6900118.html
