---
tags: 字串
title: 字串1
---

:::info
### 題目s：
*PS:前兩題可以交換作法試試看喔～*
- [洛谷 P3370 (hash 模板題)](https://www.luogu.com.cn/problem/P3370)
- [ZJ d518 (Trie 模板題)](https://zerojudge.tw/ShowProblem?problemid=d518)
- [TIOJ 1281 (hash 變形題)](https://tioj.ck.tp.edu.tw/problems/1281)
- [TIOJ 1515 (hash 變形題)](https://tioj.ck.tp.edu.tw/problems/1515)
:::
$5695138290_{(10)}$
$\sum_{i=0}^{9}10^i\times digit_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$

:::success
## 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值：
$$pre[i] = \sum_{j=0}^{i}p^{i-j}*S[j]$$
- 然後，
$$pre[j] = pre[j-1]*p+S[j]$$
- 某一段的hash：
$$hash(i,j)=pre[j] - pre[i-1]*p^{j-i+1}$$

### 補：HASH碰撞機率
- 生日問題～
- 推導過程超出高中數學範圍，在此忽略
- 碰撞機率概算公式：（$N$為字串數量，$M$為可能值得數量 || 空間 || 值域大小）
$$1-exp(-N^2/(2\times M))$$
$$1-e^{-N^2/(2\times M)}$$

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