---
# System prepended metadata

title: 字串
tags: [Todo, Algorithm]

---

字串
===
###### tags: `Algorithm` `Todo`

## 尋找子字串
* 雜湊函數
```
(ran^N-1*C1 + ran^N-2*C2... + ran^N-10*C10...)%M
```
計算字串的前綴雜湊函數
![](https://i.imgur.com/iOO76xZ.png)
* 模反元素
![](https://i.imgur.com/yppyNR3.png)

## 雜湊函數
用map值對應各個元素,
## 
![](https://i.imgur.com/9FWoivN.png)
* KMP

## 字典樹
![](https://i.imgur.com/XfVJfPu.png)
![](https://i.imgur.com/nOi3pH5.png)
![](https://i.imgur.com/WBzvoTB.png)

## AC自動機
![](https://i.imgur.com/1ppErab.png)
![](https://i.imgur.com/3uVC4WA.png)
![](https://i.imgur.com/gdLVKY4.png)

