核心概念:使用 Rolling Hash 快速比較字串。
Hash Function:h(s) = (s[0]×d^(m-1) + s[1]×d^(m-2) + ... + s[m-1]) mod q
其中 d = 字元集大小 (256),q = 質數 (101)
Rolling Hash:h(i+1) = (d × (h(i) - s[i]×d^(m-1)) + s[i+m]) mod q
可以在 O(1) 時間內計算下一個視窗的 hash。
複雜度:平均 O(n+m),最差 O(nm)(hash 碰撞時需字元比較)