廣義后綴自動機(jī)的前置知識點(diǎn)是后綴自動機(jī)和字典樹（Trie樹）的相關(guān)內(nèi)容，因?yàn)檫@兩個知識點(diǎn)穿插在一起更容易理解和構(gòu)建知識框架。

當(dāng)我們的是動機(jī)如何儲存一個字符串的所有子串？該怎么辦？怎么做？后綴自動機(jī)的作用就展現(xiàn)出來了。

首先，后綴自動機(jī)起源于劉研繹在其 2015 國家隊(duì)論文《后綴自動機(jī)在字典樹上的拓展》上提出的一種結(jié)構(gòu)，即將后綴自動機(jī)直接建立在字典樹上。

廣義SAM是一種用于維護(hù)Trie的子串信息的SAM的簡單變體。將多個模式串插入到Trie后，即可使用廣義SAM維護(hù)多模式串的信息。這是廣義SAM最廣泛的應(yīng)用之一，其基本思想是將多串的信息進(jìn)行壓縮，使得SAM在仍滿足節(jié)點(diǎn)數(shù)最少的同時 包含所有子串的信息。此時SAM中的一個狀態(tài)可能同時代表多個串中相應(yīng)的子串。

一種顯然的做法是先使用多個模式串構(gòu)造Trie樹，再在Trie上構(gòu)建SAM。

常見的偽廣義后綴自動機(jī)：

（1）通過用特殊符號將多個串直接連接后，再建立 SAM；

（2）對每個串，重復(fù)在同一個 SAM 上進(jìn)行建立，每次建立前，將last指針置零。

方法1和方法2的實(shí)現(xiàn)方式簡單，而且在面對題目時通?？梢赃_(dá)到和廣義后綴自動機(jī)一樣的正確性。所以在網(wǎng)絡(luò)上很多人會選擇此類寫法，例如在后綴自動機(jī)一文中最后一個應(yīng)用，便使用了方法1 。

但是無論方法1還是方法2，其時間復(fù)雜度較為危險。

字典樹的使用也是尤為需要注意的一點(diǎn)，首先應(yīng)對多個串創(chuàng)建一棵字典樹，這不是什么難事，如果你已經(jīng)掌握了前置知識的前提下，可以很快的建立完畢。這里為了統(tǒng)一上下文的代碼，給出一個可能的字典樹代碼。

后綴自動機(jī)的建立：如果我們把這樣一棵樹直接認(rèn)為是一個后綴自動機(jī)，則我們可以得到如下結(jié)論：

對于節(jié)點(diǎn)i，其 len[i] 和它在字典樹中的深度相同

如果我們對字典樹進(jìn)行拓?fù)渑判?，我們可以得到一串根?jù) len 不遞減的序列。BFS的結(jié)果相同。