算法提高 周期字串 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB 提交此題 問(wèn)題描述 右右喜歡聽(tīng)故事，但是右右的媽媽總是講一些“從前有座山，山里有座廟，廟里有個(gè)老和尚給小和尚講故事，講的什么呢？從前有座山……”這樣循環(huán)的故事來(lái)搪塞右右。 我們定義，如果一個(gè)字符串是以一個(gè)或者一個(gè)以上的長(zhǎng)度為k的重復(fù)字符串所連接成的，那么這個(gè)字符串就叫做周期為k的串。 例如: 字符串’abcabcabcabc’周期為3，因?yàn)樗怯?個(gè)循環(huán)’abc’組成的。它同樣是以6為周期（兩個(gè)重復(fù)的’abcabc’）和以12為周期（一個(gè)循環(huán)’abcabcabcabc’）。 右右現(xiàn)在想給他的朋友大灰狼轉(zhuǎn)述媽媽講的故事，請(qǐng)幫他寫(xiě)一個(gè)程序，可以測(cè)定一個(gè)字符串的最小周期。 輸入格式 一個(gè)最大長(zhǎng)度為100的無(wú)空格的字符串。 輸出格式 一個(gè)整數(shù)，表示輸入的字符串的最小周期。 樣例輸入 HaHaHa 樣例輸出 2 樣例輸入 Return0 樣例輸出 7
暴力枚舉，一個(gè)個(gè)的長(zhǎng)度枚舉
#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++)//枚舉長(zhǎng)度 { 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; }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
