超長字元串中如何快速查找一個子串？

01-04

我初始化了一個含有3億個隨機小寫字母組成的字元串，現在我要隨機查找一個自定義長度的字元串是否在這個串中，該用什麼演算法？

題主首先要確定的是，到底是在一大堆超長字元串裡面找一個字串，還是在一個超長字元串裡面找一堆字串，演算法是不一樣的。

不過本質上都是一樣的，給固定的那個字元串做狀態機，演算法的名字多種多樣。

如果是這種長串固定，短串可變的可以考慮後綴樹。

但是後綴樹可能太大了所以考慮一些更節省空間的後綴樹，具體自己搜索關於 succinct suffix tree

KMP演算法……

單模匹配的最佳演算法了

預處理時間複雜度是 $O(lenb)$ 的

總時間複雜度是 $O(lena+lenb)$ 的

公式改過來了,好看多了QAQ

（1）Boyer-Moore 演算法

示意圖1

複雜度1

2.KMP演算法

示意圖2

複雜度2

KMP演算法應該是漸進最優的了，恩……

參考資料：Data Structure Algorithms in Python, by Michael T.Goodrich等

BWT+FM-Index就可以了

不過需要先建索引後使用。。

查找是在壓縮文件上的，速度很快

不過3億個字母也沒多少吧。。可能不需要壓縮。。那就上KMP吧

rolling hash？

正則表達式

BM演算法/KMP

std::find

kmp看毛片演算法2333

看毛片演算法呀

哈哈哈我貌似看到了我們數據結構期末考試題

把它當做實現正則表達式引擎的子問題，構造狀態機吧

這種問題沒必要發知乎……百度吧……