類似于week2,3拄踪；
然后這一節(jié)題目說是Trie圖蝇恶，其實(shí)用AC自動機(jī)更容易搜出來結(jié)果。
對于一個(gè)M<=10^6的字符串惶桐；N個(gè)長度為L的單詞撮弧；
最差的辦法：
對于M枚舉起始位，采用week2的trie樹方案姚糊，嘗試在單詞trie樹上走到某結(jié)點(diǎn)贿衍；
講解比較細(xì)的版本：Trie圖
過程和kmp非常類似。
kmp的過程是:如果匹配成功救恨，那么向前平移對準(zhǔn)贸辈，next[i]=j；
如果匹配失敗肠槽，那么j=next[j],即調(diào)整到可能的匹配位置擎淤。
類似的，對于trie圖：
如果匹配成功秸仙，向前移位嘴拢；
如果匹配失敗，那么將齊位校準(zhǔn)到可能的匹配位筋栋。用來代替next數(shù)組尋找最長匹配(失敗段的后綴炊汤，也就是新匹配的前綴)位置的，就是后綴指針。(hiho說是后綴抢腐，上文引用的blog說是前綴姑曙，隨意啦)
看了看范叔叔和學(xué)弟的模板。迈倍。伤靠。壓力很大啊。
過了好tm久翻到ac自動機(jī)才又想起來我這兒還有個(gè)這 額滴神啊啼染。
趕緊解決掉宴合。。迹鹅。
捋一遍流程:
每個(gè)節(jié)點(diǎn)包括：
對應(yīng)字符串卦洽；后綴指針指向的字符串；到達(dá)后綴節(jié)點(diǎn)后每條路徑走出的字符串（包括父節(jié)點(diǎn)后綴指向得到的字符串斜棚，由bfs得出）阀蒂；
初始化：根節(jié)點(diǎn)對應(yīng)null；根節(jié)點(diǎn)及其子后綴指針也null弟蚀；
然后建樹蚤霞，查找。嗯 我選擇抄板子先义钉。
