這里的“自動(dòng)機(jī)”指的是”確定有限狀態(tài)自動(dòng)機(jī)”。而自動(dòng)機(jī)是信息學(xué)奧林匹克競(jìng)賽、計(jì)算機(jī)科學(xué)中被廣泛使用的一個(gè)數(shù)學(xué)模型，其思想在許多字符串算法中都有涉及，學(xué)習(xí)自動(dòng)機(jī)有助于理解上述算法，但是學(xué)習(xí)自動(dòng)機(jī)前一定要先了解基礎(chǔ)圖論的相關(guān)知識(shí)，這樣才更好理解自動(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-元組。

確定有限狀態(tài)自動(dòng)機(jī)一個(gè)字符接一個(gè)字符的讀入一個(gè)字符串，并根據(jù)給定的轉(zhuǎn)移函數(shù)一步一步的轉(zhuǎn)移至下一個(gè)狀態(tài)。在讀完該字符串后，如果該自動(dòng)機(jī)停在一個(gè)屬于F的接受狀態(tài)，那么它就接受該字符串，反之則拒絕該字符串。

自動(dòng)機(jī)的類型有哪些？

（1）AC自動(dòng)機(jī)

AC自動(dòng)機(jī)接受且僅接受以指定的字符串集合中的某個(gè)元素為后綴的字符串。也就是Trie + KMP。

（2）后綴自動(dòng)機(jī)

后綴自動(dòng)機(jī) 接受且僅接受指定字符串的后綴。

（3）廣義后綴自動(dòng)機(jī)

廣義后綴自動(dòng)機(jī) 接受且僅接受指定的字符串集合中的某個(gè)元素的后綴。也就是 Trie + SAM。

廣義 SAM 與 SAM 的關(guān)系就是 AC 自動(dòng)機(jī)與 KMP 自動(dòng)機(jī)的關(guān)系。

（4）回文自動(dòng)機(jī)

回文自動(dòng)機(jī)比較特殊，它不能非常方便地定義為自動(dòng)機(jī)。

如果需要定義的話，它接受且僅接受某個(gè)字符串的所有回文子串的中心及右半部分。“中心及右邊部分”在奇回文串中就是字面意思，在偶回文串中定義為一個(gè)特殊字符加上右邊部分。這個(gè)定義看起來很奇怪，但它能讓 PAM 真正成為一個(gè)自動(dòng)機(jī)，而不僅是兩棵樹。

（5）序列自動(dòng)機(jī)

序列自動(dòng)機(jī) 接受且僅接受指定字符串的子序列。

在計(jì)算復(fù)雜性領(lǐng)域中，自動(dòng)機(jī)是一個(gè)經(jīng)典的模型，要想吃透這方面的內(nèi)容，還是需要多多練習(xí)，從中找到規(guī)律。