切換
舊版
前往
大廳
主題

ZeroJudge - e537: 00455 - Periodic Strings　解題心得

Not In My Back Yard | 2019-11-19 23:23:35 | 巴幣 0 | 人氣 214
題目連結：
題目大意：
給定一正整數 N ，代表有 N 筆測試資料。每筆測資佔兩列。第一列為空白列；第二列則是給定一字串 s （s 長度最長為 80 個字元，每個字元皆是非空白字元）。

試問 s 的最短循環節為多少？

例如 abcabcabcabc ，由長度 3 的 abc 組成或是由長度 6 的 abcabc 組成，又或是由長度 12 的 abcabcabcabc 組成。所求為長度 3 的「3」之值，因為其為最短的循環節。

範例輸入：
1

HoHoHo
範例輸出：
2
解題思維：
窮舉所有可能的循環節長度，即 s 長度的因數。例如 s 的長度 12 就先從長度 1 開始試試看有無循環；沒循環就換長度 2 ；再失敗就換長度 3 、長度 4 、長度 6 ，最後是長度 12 （這個一定符合，所以也不用判斷）。其他的 s 也以此類推。

當過程中有發現有長度 i 的循環節時，該 i 值即是所求的最短循環節。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#字串#窮舉
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

團戰

看更多

相關創作

更多創作

追蹤 創作集
其他創作
作品資料夾