在我們學(xué)習(xí)后綴自動(dòng)機(jī)之前，一定要先了解什么是自動(dòng)機(jī)？自動(dòng)機(jī)（確定有限狀態(tài)自動(dòng)機(jī)）是由一個(gè)非空有限狀態(tài)的集合Q、一個(gè)輸入字母表 Σ（非空有限字符的集合）、一個(gè)轉(zhuǎn)移函數(shù)（單值映射）、一個(gè)開始狀態(tài)、一個(gè)接受狀態(tài)（終結(jié)狀態(tài)）的集合所組成的5-元組。

歷史上，Blumer等人于1983年首次提出了后綴自動(dòng)機(jī)的線性規(guī)模，然后在1985-1986年，人們提出了首個(gè)線性時(shí)間內(nèi)構(gòu)建后綴自動(dòng)機(jī)的算法（Crochemore，Blumer等）。在文末鏈接處查看更多細(xì)節(jié)。

后綴自動(dòng)機(jī)在英文中被稱作“suffix automaton”（復(fù)數(shù)形式：suffix automata），單詞的有向無(wú)環(huán)圖——"direcged acyclic word graph"（簡(jiǎn)寫為“DAWG”）。

而后綴自動(dòng)機(jī)（單詞的有向無(wú)環(huán)圖）是一種強(qiáng)有力的數(shù)據(jù)結(jié)構(gòu)，讓你能夠解決許多字符串問(wèn)題。

例如，使用后綴自動(dòng)機(jī)可以在某一字符串中搜索另一字符串的所有出現(xiàn)位置，或者計(jì)算不同子串的個(gè)數(shù)——這都能在線性時(shí)間內(nèi)解決。

直覺(jué)上，后綴自動(dòng)機(jī)可以被理解為所有子串的簡(jiǎn)明信息。一個(gè)重要的事實(shí)是，后綴自動(dòng)機(jī)以壓縮后的形式包含了一個(gè)長(zhǎng)度為n的字符串的所有信息，僅需要O(n)的空間。并且，它能在O(n)時(shí)間內(nèi)被構(gòu)造（如果我們將字母表的大小k視作常數(shù)，否則就是O(n*logk)）。

后綴自動(dòng)機(jī)的定義：對(duì)給定字符串s的后綴自動(dòng)機(jī)是一個(gè)最小化確定有限狀態(tài)自動(dòng)機(jī)，它能夠接收字符串s的所有后綴。

后綴自動(dòng)機(jī)構(gòu)建過(guò)程：

（1）我們將會(huì)在這里展示一些簡(jiǎn)單的字符串的后綴自動(dòng)機(jī)。

（2）我們用藍(lán)色表示初始狀態(tài)，用綠色表示終止?fàn)顟B(tài)。

對(duì)于字符串 s=?：

對(duì)于字符串 s=a：

對(duì)于字符串 s=aa：

對(duì)于字符串 s=ab：

對(duì)于字符串 s=abb：

對(duì)于字符串 s=abbb：

以上是后綴自動(dòng)機(jī)的一些概念和內(nèi)容，不知道大家有沒(méi)有學(xué)會(huì)，如果有什么疑問(wèn)歡迎在博客里提出。