2010年4月23日 星期五

UVa 455 Periodic Strings

解題策略

這題要找出字串中的最小週期,我的作法比較好玩一些。
首先用兩個指針i,j分別指向字串的頭兩個字母,像這樣:
abcdabcd
↑↑
我的基本想法很簡單,讓i,j之間保持一個固定間距,如果這個間距就是週期,那麼且同步往後移動指針,比對字母,i,j指的兩字母應該要一直都相同。
# 例子:不管何時,兩指針的字母皆同。
abcabcabc
↑  ↑
abcabcabc
 ↑  ↑
abcabcabc
  ↑  ↑

那麼我們的任務就是找出i, j 的間距啦。初始從週期值1開始比對兩字,不同表示尚未找到週期,拉開指針的間距一格 (++j) 。直到兩字相同 buf[i]==buf[j],這時候可能就是字串中的週期出現了,同步移動指針 (++i,++j) 持續往後比對。

這個作法有兩個Special case要考慮
  1. 字串只有一個字母的時候(長度為1),兩根指針還能指去哪,直接return 1。
  2. 有時候字串尾巴會出現一些破壞週期的字母,例如:abcabcabcd,或者hohaho。所以最後必須檢查找到的週期,跟字串長度是否恰好是倍數關係。若不能整除就表示有這種討人厭的破壞字母出現了,週期值直接等於字串長度。