算法提高 周期字串 時間限制：1.0s 內存限制：256.0MB 提交此題 問題描述 右右喜歡聽故事，但是右右的媽媽總是講一些“從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事，講的什么呢？從前有座山……”這樣循環的故事來搪塞右右。 我們定義，如果一個字符串是以一個或者一個以上的長度為k的重復字符串所連接成的，那么這個字符串就叫做周期為k的串。 例如: 字符串’abcabcabcabc’周期為3，因為它是由4個循環’abc’組成的。它同樣是以6為周期（兩個重復的’abcabc’）和以12為周期（一個循環’abcabcabcabc’）。 右右現在想給他的朋友大灰狼轉述媽媽講的故事，請幫他寫一個程序，可以測定一個字符串的最小周期。 輸入格式 一個最大長度為100的無空格的字符串。 輸出格式 一個整數，表示輸入的字符串的最小周期。 樣例輸入 HaHaHa 樣例輸出 2 樣例輸入 Return0 樣例輸出 7
暴力枚舉，一個個的長度枚舉
#include <iostream>#include <cstdio>#include <cstring>#include <iomanip>#include <cmath>#include <algorithm>#include <map>using namespace std;int main(){ string a; while(cin>>a) { int z; int mins=10000; for(int j=1;j<=strlen(&a[0])/2;j++)//枚舉長度 { if(strlen(&a[0])%j!=0) continue;//判斷字符串是否可能成周期。就是是否能除盡 z=1; int k=0; string c,d; for(;k<j;k++) c+=a[k]; while(k<strlen(&a[0])) { d+=a[k]; //cout<<c<<' '<<d<<' '<<j<<' '<<k<<endl; k++; if(strlen(&d[0])==j) { if(d==c) { d.clear(); } else { z=0; break; } } } if(z) { mins=j; break; } } if(z)cout<<mins<<endl; else cout<<strlen(&a[0])<<endl; }}新聞熱點
疑難解答
