一、有限自动机

有限状态机是一个处理信息的简单机器。通过对文本字符串 T 进行扫描，找出模式 P 的所有出现位置。给它输入一个模式串，会得到一个YES或者NO的结果。
它只对每个文本字符检查一次，并且检查每个文本字符时所需的时间为常数。因此，在模式预处理完成并建立好自动机后进行匹配所需要的时间为 O(n) 。

二、实现

一个有限自动机 M 是一个 5 元组（Q，q， A， ∑，δ）

Q 是状态的有限集合
q∈Q 是一个初始状态
A 包含于 Q 是一个特殊的接受状态集合
∑ 是有限输入字母表
δ 是一个从 Q✖∑ 到 Q 的函数，称为 M 的转移函数

例如，对于0101111001串构建一个判断1的个数是否为偶数个的有限自动机

最后结果为红色区域，表明这个是一个偶数。

又例如，对P="ababaca"构建有限自动机，如以下a图所示

对于每一状态，会根据接受字符的情况来变化。

如b图所示，左边坐标表示状态；右边表示模式串P的匹配情况；上方表示输入情况。
例如第一行：当状态为0时，此时匹配的是P串的字符a。当输入为a时，转入状态1；输入为b，c时，转入状态0.

如c图所示：表示的是文本串T的匹配情况。在文本串之下的是状态的情况，当状态为7时，匹配成功。

P：模式串（要找到的串）
∑：有限的字母表（对于一个串，我们应该知道其出现了多少种字母，如aabcc的字母表为a、b、c）
k：根据状态q和输入的字符的不同，所设置的该转移到的状态

双层for在做的事：对于每一个状态q，又对于每一个字母表中的字符，k为最可能的最大状态（要么是当前状态q+2，要么是长度m加1，注意这里多了1），然后k自减，直到Pk是Pq合上字符a的后缀时，设置状态函数状态。（参考KMP找最长公共前后缀）

简单来说，就是对于文本串的每一个字符，不断更新当前状态q，当q为模式串长度m时，说明找到串了。