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題庫目錄
回首頁