鏈接放在這里，有點難理解，至少我個人是的。
后綴自動機是一種有限狀態(tài)自動機，其功能是識別字符串是否是母串的后綴。它能解決的問題當然不僅僅是判斷是不是后綴這種事，跟字符串的連續(xù)子串有關的問題都可以往這個方面考慮，畢竟字符串的每個連續(xù)字串都可以看做是兩個長度不同的后綴去掉他們的公共部分得到的。
自動機由五個部分組成：alpha：字符集，state：狀態(tài)集合，init：初始狀態(tài)集合，end：結束狀態(tài)集合，trans：狀態(tài)轉移函數(shù)。
定義trans(s,ch)為當前狀態(tài)為s，讀入字符ch后所達到的狀態(tài)。若不存在此轉移，則將轉移的結果定義為null，表示不存在的狀態(tài)。自動機A能識別的字符串就是所有使得trans(init,x)∈end的字符串，令這些字符串組成的集合為Reg(A)。另外，對于自動機中的某一狀態(tài)s，從s開始能識別的字符串記為Reg(s)。
