← 返回首頁
Rolling Hash 滾動雜湊
模式匹配
最長公共子字串
碰撞檢測
文字：
模式：
搜尋
逐字元計算雜湊
預設：
自訂
Rabin-Karp 範例
重複模式
DNA 序列
字串 A：
字串 B：
計算 LCS
字串：
最大長度：
分析碰撞
字串視覺化
雙雜湊比較
使用兩組不同的 (base, mod) 降低碰撞機率：
Hash1: base=131, mod=10^9+7
Hash2: base=137, mod=998244353
演算法說明
Rolling Hash (滾動雜湊)
將字串映射為整數，用於快速比較子字串。
多項式雜湊：hash(s) = s[0]*p^(n-1) + s[1]*p^(n-2) + ... + s[n-1]*p^0 (mod m)
前綴雜湊：預處理 O(n)，任意子字串雜湊 O(1)
Rabin-Karp 模式匹配：O(n + m)
雙雜湊降低碰撞率至約 1/(10^18)
最長公共子字串：二分搜尋 + 雜湊，O((n+m) log min(n,m))