抄襲偵測器 - Rabin-Karp ← 返回遊戲列表
Text (文本)
Pattern (模式)
Pattern Hash
-
Window Hash
-
Hash = Σ (char × base^i) mod prime
0
Hash 比較次數
0
字元比較次數
0
匹配數

Rabin-Karp 演算法

核心概念:使用 Rolling Hash 快速比較字串。

Hash Functionh(s) = (s[0]×d^(m-1) + s[1]×d^(m-2) + ... + s[m-1]) mod q
其中 d = 字元集大小 (256),q = 質數 (101)

Rolling Hashh(i+1) = (d × (h(i) - s[i]×d^(m-1)) + s[i+m]) mod q
可以在 O(1) 時間內計算下一個視窗的 hash。

複雜度:平均 O(n+m),最差 O(nm)(hash 碰撞時需字元比較)