2010年3月7日 星期日

Problem 455 Periodic Strings,字串的最小週期

此題是要找出字串的最小週期。例如 abcabc 有兩種週期,一由子字串 abc 重複 2 次(週期為 3),二由子字串 abcabc 重複 1 次(週期為 6)。在這例子中,要輸出 3,因為它為字串的最小週期。

稍微想一下,可以知道只要是字串長度的因數,都有可能是字串的週期。所以可以寫一個函式,傳入字串與字串的因數,去找尋與它相對位置互相比較是否相等,若不相等,則不為此字串週期;若皆相等,則為子字串週期。

以下為此題關鍵函式:
int strPeriod(char str[], int j)
{
int i;
for (i = j; i < strlen(str); i ++)
if (str[i] != str[i % j]) break;
if (i == strlen(str)) return 1;
else return 0;
}


而主程式只需如此呼叫函式:
gets(str);
length = strlen(str);
for (j = 1; j < length; j ++)
{
if (length % j == 0)
if (strPeriod(str, j) == 1)
break;
}
printf("%d\n", j);

此題最需注意的地方就是輸出的格式,因為格式是 Online Judge 最 GY 的地方,多一個空白或換行都不行,所以要多試幾次。

By David.K

p455題目連結
回ACM題庫目錄
回首頁

沒有留言: