UVa1328 - Period

出處：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4074

解題策略：KMP(Knuth–Morris–Pratt algorithm)

aabaabaabaab的KMP演算法fail陣列為0,0,1,0,1,2,3,4,5,6,7,8,9，以最後一個9來看，表示12個字元的前9個與後9個相同，如下圖，f[6]等於3表示6個字元時，前3個與後3個相同，則A=B，f[9]等於6表示9個字元時，前6個與後6個相同，則B=C，同理C=D，所以A=D，所以找出12個字元時，有發現長度為3的循環，重複4次。獲得以下推論，i等於12，i-f[i]為3，i%(i-f[i])等於0，表示長度12的前缀，每3個字元重複一次，重複4次。