天天看點

[kmp例題] poj2406 Power Strings

題意:求出字元串的最大循環次數,例如abababab是4

我們考慮求next數組時,上下兩個字元串不重疊的部分長度為t = len - next[len]

觀察重疊部分,則下方字元串的[1,t] = 上方的[t+1,2t], 下方字元串的[t+1,2t] = 上方的[2t+1,3t], ...

如果len - t是t的整數倍,則可以得到字元串循環節的長度為t,否則沒有循環節。