简(kun)单(nan)到让我开(jue)心(wang)的后缀自动机全家桶（普通后缀、广义后缀、子序列）...
目錄
- 參考文獻
- 后綴自動機是什么神仙玩意？
- 例題
- right集合、等價類以及Parent樹
- 定義
- 等價類性質
- Trie？DAG？
- 自動機？自動雞？
- 自動機的基本性質
- 一定存在后綴自動機嗎？
- 后綴自動機是唯一的嗎？
- 后綴自動機的幾個性質
- 邊的數量級
- 構造方法
- 代碼
- 部分1
- 部分2
- 部分3
- 部分4
- 部分5
- 思路
- 代碼
- 時間復雜度
- 廣義后綴自動機
- 思路
- 練習
- 子序列自動機
參考文獻
咕咕日報上的，就沒有一個是差品：https://www.luogu.org/blog/Kesdiael3/hou-zhui-zi-dong-ji-yang-xie，同時，帶luogu水印的圖也是一律采用這個博客的，因為我太弱了，不會畫圖QAQ。
時間復雜度的證明https://blog.csdn.net/qq_35649707/article/details/66473069
廣義后綴數組就是在這學的：https://blog.csdn.net/litble/article/details/78997914
字符集的相關內容：https://oi.men.ci/suffix-automaton-notes/
套B-樹：https://www.cnblogs.com/hyghb/p/8445112.html
stO 后綴自動機怎么能少了陳立杰大佬的論文了呢? Orz
博主是真的臭不要臉，拿著別人的圖寫著自己的博客
后綴自動機是什么神仙玩意？
其實許多題目，我們都可以用后綴數組做，但是后綴數組有時候遠遠不能滿足我們的需求，這個時候，后綴自動機就出現了。
例題
問題描述 給出一個字符串S(S<=250000)，令F(x)表示S的所有長度為x的子串中，出現次數的最大值。求F(1)..F(Lengh(S)); 樣例輸入 ababa 樣例輸出 3 2 2 1 1right集合、等價類以及Parent樹
定義
首先，我們要定義一個東西，叫\(right\)，字符串的每個子串都可以有個\(right\)。
\(right(s)\)表示的是\(s\)子串在母串所有出現位置的右端點。
打個比方：在\(ababa\)中，\(right(ab)={2,4}\)
等價類性質
1
加入有兩個不相同的子串的\(right\)集合是相等的，那么必然一個是另外一個的后綴。
這個挺好證的，感性理解最好，畫個圖就知道了。
我們把所有相同的\(right\)集合叫做一個等價類。
如圖，\(ab,b\)就是在一個等價類里面。
2
兩個\(right\)集合，要么兩個集合沒有相同的數字，要么一個集合是另外一個集合的子集。
這個也挺好證的，用反證法，如果\(right\)集合中有一個相等的，那么我們就可以進而推出一個是另外一個的后綴（自己想想看是不是），那么在想想看是不是一個子串的\(right\)是不是就是那個作為后綴子串的\(right\)的子集。
3
對于每個\(endpos\)（等價類）而言，里面所包含的子串的長度應當是連續的。
假設子串的長度是不連續的，那么設這個不在里面的子串是\(s\)，那么比他短的子串在這個等價類里面，也就是說只有這個\(right(s)\)數字的個數小于\(endpos\)里面子串\(right\)的數字個數，才可以，但是比他長的子串也在里面，而這個子串無一例外是這些比他長的子串的后綴，所以只能數字個數只能等于，所以這個\(s\)應當在等價類里面。
4
等價類點的個數的數量級是\(O(n)\)的。
我們可以發現，在一個\(endpos\)里面最長的子串前面加一個字符，就是另外一個\(endpos\)里面的，而這個\(endpos\)里面的\(right\)集合應該是原來\(endpos\)里面的\(right\)集合的子集，因為這個新子串要出現肯定是要這個舊子串的基礎上還有個字符相等才可以的。
而我們在舊子串前面添加另外一個不一樣的字符，得到的\(endpos\)的\(right\)和原來的新子串\(endpos\)的\(right\)是不相交的，怎么可能有個位置使得兩個長度相同但不一樣的子串都出現呢？
所以我們可以知道，一個等價類的\(right\)集合通過正確的分割，可以分割成幾個其他\(endpos\)的\(right\)集合。
那么從\({1,2,3,...,n}\)，開始分割，最多也只能像線段樹那樣分（為什么，倒著想，兩個葉子結點就可以產生一個父親節點，這是最多的合并方案了），也是最多就\(O(n)\)個罷了，所以節點數量最多\(O(n)\)。
而這個巧妙的分裂方案又呈現出一個樹的樣子，那么我們就給這棵樹起個文雅點的名字：\(Parent Tree\)。
同時一個字符串只有唯一的\(Parent\)樹，因為等價類的劃分只有一個。
LOOK一下\(aababa\)的\(Parent\)樹
點里面的就是\(right\)集合，什么？\(1\)的點為什么不見了？因為\(right\)為\(1\)的子串為\(a\)，很不巧的是剛好被\(1,2,4,6\)給包含了進去，但是并不會影響我們，只要以后想題的時候注意一下就行了。
5
我們設等價類里面最長的子串長度是\(len\)，最短的是\(minlen\)，那么\(len(fa(x))+1=minlen(x)\)，其實這個也挺好證明的，兒子最短的子串就是自己最長的子串加一個字符嗎，對吧。
Trie？DAG？
我們都知道，有個強大的Trie，我們可以把一個字符串的每個后綴插入進去，然后就成了這樣(aabab)：
他可以支持查詢任意一個子串，子串個數等等操作。
為什么？
因為他有以下的性質：
但是點的個數是\(O(n^2)\)的，那么我們要如何處理這個問題呢。
那么我們就得找到一個符合這個性質的一個好東西。
而且我們也發現上圖中的\(abab\)中的\(bab\)可以和其他的\(bab\)結合的。
也就是說我們可以找到一個在\(DAG\)上的一種算法，而不是一棵樹。
當然也就是后綴自動機，同時因為他有更多的性質，使得他更加的強大。
當然，特別巧的是，后綴自動機的節點就是\(Parents\)樹上面的，邊就不是了，邊就讓我們和眼花繚亂了，而在構造的時候，我們也是用兩種理論互相完善形成的。
給出一個圖：
自動機？自動雞？
談到雞就不禁想到了jntm，自動jntm？
自動機的基本性質
首先，自動機一般有這么五個東西：初始狀態，狀態集合，結束狀態，轉移函數，以及字符集。
那么字符集我們知道，初始狀態和結束狀態呢？初始狀態我們設為空串，也就是\(right\)集合\({1,2,3,4...,n}\)，而結束狀態則是集合內一個個的后綴，也就是\(Parent\)樹中\(right\)集合為\(n\)的以及他的父親與祖先，除了根節點。
而轉移呢，從一個節點\(x\)到另外一個節點\(y\)連一條為\(c\)的邊出來，表示的是\(x\)包含的所有子串在后面加上\(c\)后都是\(y\)中所包含的子串（但\(y\)中的子串去掉最后一個字符不一定是\(x\)中的子串，只有可能是\(x\)兒子所包含的子串）。
字符集不就是那個母串嗎。
大佬：還以為有多術語，沒想到還是口頭語。
那么一個成型的后綴自動機大概長這樣：
橙點是結束狀態，每個點旁邊的紅色字符串表示的是最長的子串。
一定存在后綴自動機嗎？
我們回想起來后綴自動機必須遵循的幾個性質：
前面三個都可以手動滿足，但是在滿足前三個性質后，第四個性質能不能滿足？
我們可以發現每個\(endpos\)所含的子串都是不同的，但是同時所有\(endpos\)所含的子串累加起來就是母串的所有不重復子串數量的和。
所以轉移我們都是在一部分子串的后面加上一個字符到達的，不可能有兩個點含有相同的子串，而且到達一個點形成的子串只能是這個點\(endpos\)所含有的，這不就證出來了？
后綴自動機是唯一的嗎？
我不敢保證絕對唯一，只能證在\(Parent\)樹上的后綴自動機是絕對唯一的，首先\(Parent\)樹是唯一的，而能指向一個\(endpos\)的\(endpos\)數量也是固定的，所以后綴自動機是唯一的。（好草率呀。）
后綴自動機的幾個性質
這里總結一下性質，方便下個證明（Trie的性質就不搬了，反正后綴自動機也是滿足的），也方便做題：
邊的數量級
后綴自動機邊的數量級是\(O(n)\)的，為什么，我們對一個后綴自動機求一個生成樹出來，刪掉其他的邊。
然后從每個終點往源點跑自己所包含的子串，往回跑的意思是找到跑到這個終點能形成這個子串的路徑，然后往會跑，允許找不到的路可以往回走的時候，可以添加一條邊回來，那么我們就可以再次走完一個子串，但是可能不是這個子串，但是我們可以先把走完的子串劃掉，然后再跑現在的子串，可以證明，跑完這個終點所有的子串（其實就是母串的后綴），添加回來的新邊不會超過這個終點所包含的子串個數。
大家弄不懂為什么添加了一條邊就又可以跑出一個子串出來？我們看一下，在生成樹上多連一條邊出來，那么是不是就是多了一條路徑可以到終點了？根據前面的性質我們知道肯定是個不同的子串，所以就可以跑出一個新的子串，所有的終點跑完后，添加的邊數不超過\(n\)條（其實這個利用性質的證法我認為更簡單，也是我的證法）。
所以數量級為\(O(n)\)。
這里草率的放個形象生動的生成樹例子在這，因為我覺得我的證法好像和他的不是很一樣。
橙點是終點，神奇顏色的點是源點，黑邊是生成樹的邊，藍邊是要添加回來的邊，綠邊是刪掉未添加回來的邊，箭頭指向的就是目前要跑的終點，注意是反著跑。
圖可能畫的不是很標準，只是為了呈現出一個加邊多路徑的一個情況出來。
我們會發現，加了一條邊，就多出現了一條路徑，也就多了個子串可以走回去。
所以我們就證明出來了。
構造方法
代碼
終于到了最后的時刻，通過看大佬的博客，我發現代碼放前面更容易幫助人理解構造的過程。
所以先放上代碼。
struct node {int a[30],len,fa; }tr[N];int tot=1,last=1; void add(int c) {int p=last;int np=last=++tot;tr[np].len=tr[p].len+1;for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;if(!p)tr[np].fa=1;else{int q=tr[p].a[c];if(tr[q].len==tr[p].len+1)tr[np].fa=q;else{int nq=++tot;tr[nq].fa=tr[q].fa;tr[q].fa=nq;tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a));tr[np].fa=nq;for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;}} }后綴自動機的構建是在線的，也就是把字符串一個個字符丟進去，進行構建。
我們跟著KesdiaelKen大佬一起，分成一個個部分來進行傳教講課。
部分1
int p=last;int np=last=++tot; tr[np].len=tr[p].len+1;我們知道，扔進去一個字符，那么會改變的肯定就是原字符串的后綴，那么我們就用\(las\)記錄包含有原字符串母串的點是哪個點，然后新點\(np\)的最長子串的長度就是新串的長度就是舊串的長度+1。
部分2
for(;p && !tr[p].a[c];p=tr[p].fa/*fa表示的是Parent樹中的*/)tr[p].a[c]=np;我們通過跳\(p\)的父親，使得每一個原本的終點（含有后綴的點）都有一條指向\(np\)的邊，也就是使所有原本的后綴都可以跳到現在的后綴集合。
\(!tr[p].a[c]\)這句話是什么意思呢？如果有個終點也有一條邊是指向\(c\)的，首先可以說明的是這個終點包含的后綴在原串中出現了至少兩次，否則在舊串中一個后綴，是不可能再在后面加點的，而且也說明了，新串的后綴有一部分已經出現過了，就要進行一些新的判斷了。
部分3
if(!p)tr[np].fa=1; else很簡單，說明原串從未有\(c\)這個數字出現（有的話\(1\)號點會指過去），所以這個新串的所有后綴都在一個\(endpos\)里面，也就是說新串只有一個終點。
當然，跳進了那個\(else\)的話，就代表了新串也不只有一個終點了。
部分4
int q=tr[p].a[c]; if(tr[q].len==tr[p].len+1)tr[np].fa=q;首先，我們知道\(p\)所代表的子串都是舊串的后綴，如果\(q\)的最長長度是\(p\)的\(+1\)，那么說明\(q\)所代表的的子串都是舊串的后綴\(+c\)，自然\(np\)就可以認他做父親。
這是你又會問了，但是\(q\)只能代表\(np\)的一些后綴呀，比如新串是\(dbcabcabc\)，然后假設\(q\)表示的是\({bc}\)這個后綴，但是他有個兒子（\(Parent\)樹的兒子）表示的又是\({abc}\)，那么根據后綴自動機\(np\)不應該認這個兒子嗎？
設這個兒子為\(q'\)，我們知道后綴自動機的話層數越深，所代表的子串長度越長，那么指向\(q'\)的一個后綴應該是\(ab\)，那么理論上將找到\(ab\)會比找到\(b\)更先，所以認的原本就是最兒子的那個。(:霧
但是你認完了以后也沒有繼續去上面更新又是怎么一回事，因為上面的后綴肯定都是小于\(tr[p].len\)的了，也就是說以后如果要找新串后綴的話，如果長度小于等于\(tr[q].len\)的話，那么找到的自然就是\(q\)了，那么我們還何必屁顛屁顛的再去加一種方式呢？破壞性質還變慢，賠了夫人又折兵。這么虧的勾當我們才不做呢，認完就完事了。
部分5
int nq=++tot; tr[nq].fa=tr[q].fa;tr[q].fa=nq; tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a)); tr[np].fa=nq; for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;那么如果\(tr[q].len≠tr[p].len+1\)，我們知道，這個時候只有\(tr[q].len>tr[p].len+1\)的情況了。
但是同時這個長的串也不是新串后綴，為什么？因為如果是的話，去掉最后一個字母比\(tr[p].len\)還大，所以應該先被跳到才對，為什么現在還沒有被跳到呢？因為這個長的串由最后\(tr[p].len+1\)個字母組成的后綴是新串后綴，但是這個長的串不是。
那么我們就涉及到了一個問題了，這個點現在出現了鍋了，我們需要把他拆成兩個點了，因此申請了一個\(nq\)，然后\(nq\)表示的就是這個點的\(tr[p].len+1\)的后綴以及更短的后綴，因為這些子串在后面又出現了一次，而\(q\)因為少了這一次，所以他的\(right\)是\(nq\)的子集，理所應當成為了他的兒子，而根據分割要求，所以\(nq\)的\(right\)還有個數字沒有分出去，就是現在新串的長度，剛好，我們的\(np\)的父親也可以認到\(nq\)身上，這不就解決了嗎。
同時雖然分開了，但是能在后面添加的數字還是可以添加的，于是我們可以把\(q\)的\(a\)數組直接拷貝到\(nq\)上面去。
不對，還有個問題，\(p\)以及\(p\)的父親祖先的\(c\)都指向了\(q\)，那么因為\(q\)以前包含了\(tr[p].len+1\)這個長度的后綴，但是現在沒有了，跑到\(nq\)上去了，所以我們自然需要用到for然后去更新一下父代。
那么這不就好起來了嗎？QMQ
思路
而例題，則十分的明顯，就是叫我們把每個點的\(right\)集合處理出來，然后拿集合大小去更新\(ans[tr[i].len]\)，然后再把\(ans\)從上到下更新一遍。
我也忘記了我到底想到了一個什么SB的思路，反正忘記了，就不管了吧。
正解就是每次在創\(np\)是，對\(np\)的\(right\)集合的個數++，我們可以知道，一個非葉子結點，他的\(right\)集合的大小就是所有兒子的\(right\)集合的大小，加上自己本身的\(right\)集合的大小。
為什么要算上自己的，自己的不是沒有嘛，因為存在掉葉子結點的情況，上文我們有提到\(1\)的葉子結點被包括在了其他節點里面，這就是我所說的考慮這種情況，這種情況一般不會對結果造成影響，但是過程可能要有點變動。
代碼
#include<cstdio> #include<cstring> #define N 510000 using namespace std; struct node {int a[30],len,fa; }tr[N];int tot=1,last=1; char st[N];int n; int dp[N],r[N]; void add(int c) {int p=last;int np=last=++tot;r[np]++;tr[np].len=tr[p].len+1;for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;if(!p)tr[np].fa=1;else{int q=tr[p].a[c];if(tr[q].len==tr[p].len+1)tr[np].fa=q;else{int nq=++tot;tr[nq].fa=tr[q].fa;tr[q].fa=nq;tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a));tr[np].fa=nq;for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;}} }//后綴自動機 inline int mymax(int x,int y){return x>y?x:y;} inline int mymin(int x,int y){return x<y?x:y;} int cs[N],sa[N]; int main() {scanf("%s",st+1);n=strlen(st+1);for(int i=1;i<=n;i++)add(st[i]-'a');for(int i=2;i<=tot;i++)cs[tr[i].len]++;for(int i=1;i<=n;i++)cs[i]+=cs[i-1];for(int i=2;i<=tot;i++)sa[cs[tr[i].len]--]=i;int p=1;for(int i=tot;i>=1;i--)r[tr[sa[i]].fa]+=r[sa[i]];//以上按深度排序的部分其實是可以直接一發DFS暴力解決的，但是這樣打也可以。for(int i=2;i<=tot;i++)dp[tr[i].len]=mymax(dp[tr[i].len],r[i]);for(int i=1;i<=n;i++)printf("%d\n",dp[i]);return 0; }時間復雜度
你問我時間復雜度？我們可以發現能影響時間復雜度的就這兩句話：
for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;第一句因為是加邊，所以不會總體不會大于\(O(n)\)。
更嚴謹的證明，跳\(for\)循環\(last\)的層數會減，而二操作最多層數\(+1\)，所以是\(O(n)\)
第二句話我們考慮\(short(x)\)表示的是\(x\)這個點的最短子串的長度，\(fa(x)\)為\(tr[x].fa\)，那么我們接著考慮一下\(short(fa(last))\)會有怎樣的變化。
我們知道原循環有兩個\(if\)，兩個\(else\)，三種情況。
如果跳到第一種情況，那么\(short(fa(last))\)就會等于0.
如果在第二種情況，我們考慮一下\(p\)在哪，在加字符前，我們會發現\(short(p)<=short(fa(last))\)，為什么會相等，因為\(p\)有可能就是\(fa(last)\)，然后跳到了\(q\)，因為只加了一個字符，所以\(short(q)<=short(p)+1\)，所以在我們可以知道\(short(nq)<=short(fa(last))\)（沒加新字符的\(last\)），所以我們就可以知道，在第二種情況下，我們的\(short(fa(last))\)會\(+1\)或者更小。
第三種情況下，我們同樣可以知道\(short(q)<=short(p)+1\)，然后把\(q\)拆成了\(q\)和\(nq\)，同時我們不是要往上跳嗎，我們知道中父親的short肯定是比兒子要少\(1\)的（不管是Parent Tree還是后綴自動機），然后我們也知道這個for循環的重定向是把原來指向\(q\)的指向與\(nq\)了。
而我們的for會跳幾層幾層呢？仔細想想最多不就是\(short(p)+1-short(q)+1\)嗎，因為你從\(p\)開始跳的話，\(short(p)\)會不斷減少，如果\(short(p)+1\)還小于\(short(q)\)的話，那么不就指不到\(q\)了嗎，所以只會跳\(short(p)-short(q)+2\)，而最壞情況\(short(p)=short(fa(last))\)，而我們新的父親就是\(nq\)，仔細想想發現跳的次數\(-1\)就是\(short(fa(last))\)減少的個數。
所以總結下來，\(n\)次調用，最多出現\(n\)個\(1\)，所以減少的也是最多\(n\)次，可以得出為\(O(n)\)。
中間不是有個拷貝嗎？但是那是字符集的大小，也就是說字符集固定的話復雜度是線性的。
不固定呢？我們可以給每個節點用map呀，當然也有大佬用B-樹的。
這里用上https://www.cnblogs.com/hyghb/p/8445112.html大佬的話
首先，我們曾經說過要保證字母表的大小是常數。否則，那么線性時間就不再成立：從一個頂點出發的轉移被儲存在B-樹中，它支持按值的快速查找和添加操作。因此，如果我們記字母表的大小是k，算法的漸進復雜度將是O(n*logk)，空間復雜度O(n)。但是，如果字母表足夠小，就有可能犧牲部分空間，不采用平衡樹，而對每個節點用一個長度為k的數組（支持按值的快速查找）和一個動態鏈表（支持快速遍歷所有存在的鍵值）儲存轉移。這樣O(n)的算法就能夠運行，但需要消耗O(nk)的空間。因此，我們假設字母表的大小是常數，即，每個按字符查詢轉移的操作、添加轉移、尋找下一個轉移——所有這些操作我們都認為是O(1)的。廣義后綴自動機
思路
我們只要每次塞入一個字符串之后，然后把last=1，然后再塞，仔細想想也滿足能都識別任意一個字符串的子串。
練習
例題
我們給每個點開個\(set\)存一下以這個點包含的所有串為子串的字符串有哪些，這些可以直接用啟發式合并合并出來，如果大于等于\(k\)的話，那么我們就處理他的val為他所包含的字串個數。
然后我們可以知道一件事情，就是加入一個點是可以的話，那么再Parent樹的父親也滿足條件，而且我們知道Parent樹中一個點的子樹里面所有由\(np\)組成的點（不包括\(nq\)的點）的個數就是這個點\(right\)集合的個數，所以我們只要DFS遍歷一下統計答案。
#include<cstdio> #include<cstring> #include<set> #include<algorithm> #define N 210000 using namespace std; struct node {int y,next; }a[N];int len,last[N]; void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;} struct SAM {int a[30],len,fa,id; }tr[N];int tot=1,las; set<int>ss[N]; void add(int id,int c) {int p=las;int np=las=++tot;tr[np].len=tr[p].len+1;ss[np].insert(id);tr[np].id=id;for(;p && !tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np;if(!p)tr[np].fa=1;else{int q=tr[p].a[c];if(tr[q].len==tr[p].len+1)tr[np].fa=q;else{int nq=++tot;tr[nq].fa=tr[q].fa;tr[q].fa=nq;tr[nq].len=tr[p].len+1;memcpy(tr[nq].a,tr[q].a,sizeof(tr[nq].a));tr[np].fa=nq;for(;p && tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq;}} } set<int>::iterator ii; long long val[N];int n,m; void dfs1(int x) {for(int k=last[x];k;k=a[k].next){int y=a[k].y;dfs1(y);if(ss[y].size()>ss[x].size())swap(ss[x],ss[y]);//減少常數for(ii=ss[y].begin();ii!=ss[y].end();ii++)ss[x].insert(*ii);ss[y].clear();//順便清空}if(ss[x].size()>=m)val[x]=tr[x].len-tr[tr[x].fa].len; } long long ans[N]; void dfs2(int x,long long zz) {zz+=val[x];if(tr[x].id)ans[tr[x].id]+=zz;//說明他是npfor(int k=last[x];k;k=a[k].next)dfs2(a[k].y,zz); } char st[N]; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",st+1);int slen=strlen(st+1);las=1;//別忘了for(int j=1;j<=slen;j++)add(i,st[j]-'a');}for(int i=2;i<=tot;i++)ins(tr[i].fa,i);dfs1(1);dfs2(1,0);for(int i=1;i<n;i++)printf("%lld ",ans[i]);printf("%lld\n",ans[n]);return 0; }子序列自動機
這里說說，子序列按順序，但是不一定是連續的，懂吧。
放上https://blog.csdn.net/litble/article/details/78997914的介紹，寫的很好
后綴自動機的一條路徑是原串的一個子串，那么序列自動機上的一條路徑就是原串的一個子序列
序列自動機很好寫，就是每次查看最后出現過的一些表示字母x的節點，如果它們沒有當前插入的字符y的兒子，那么就將它們的y兒子賦為當前節點，顯然這樣可以表示出原串的所有子串。
轉載于:https://www.cnblogs.com/zhangjianjunab/p/11411543.html
總結
以上是生活随笔為你收集整理的简(kun)单(nan)到让我开(jue)心(wang)的后缀自动机全家桶（普通后缀、广义后缀、子序列）...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【SDOI2008】Sandy的卡片（后
- 下一篇： keras冒bug