字串 === ###### 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)