字串1 - HackMD

題目s：

PS:前兩題可以交換作法試試看喔～

5695138290_{(10)}

\sum_{i = 0}^{9} 10^{i} \times d i g i t_{i}

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

A_{1}, A_{2}, . . ., A_{n}

S_{1} = A_{1}

S_{2} = A_{1} + A_{2}

S_{3} = A_{1} + A_{2} + A_{3}

S_{4} = A_{1} + A_{2} + A_{3} + A_{4}

S_{5} = A_{1} + A_{2} + A_{3} + A_{4} + A_{5}

Hash

字串編碼！！
這裡使用 Rabin-Karp rolling hash
字串
$S$ 長度
$n$
假設質數
$p = 65537$ ，
$M = 10^{9} + 7$
記得都要取模

$\sum_{i = 0}^{| S | - 1} p^{i} \times S [i]$

$\sum_{i = 0}^{| S | - 1} p^{| S | - 1 - i} \times S [i]$
前綴hash值：

$p r e [i] = \sum_{j = 0}^{i} p^{i - j} * S [j]$
然後，

$p r e [j] = p r e [j - 1] * p + S [j]$
某一段的hash：

$h a s h (i, j) = p r e [j] - p r e [i - 1] * p^{j - i + 1}$

補：HASH碰撞機率

生日問題～
推導過程超出高中數學範圍，在此忽略
碰撞機率概算公式：（
$N$ 為字串數量，
$M$ 為可能值得數量空間值域大小）

$1 - e x p (- N^{2} / (2 \times M))$

$1 - e^{- N^{2} / (2 \times M)}$

Trie

就是字典樹～
圖片來源：https://github.com/Vercaca/Trie
實做遇到困難可以相互討論一下喔～