在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表
确定有限状态自动机
所组成的5-元组。因此一个DFA可以写成这样的形式：
确定有限状态自动机从起始状态开始，一个字符接一个字符地读入一个字符串
上图为模式串 ACACAGA的有限状态机状态转换图
从状态0到状态7，每次输入一个字符，都会让状态机从一个状态转移至另一个状态，直到状态7，说明模式完全匹配，例如，此时处于状态3，如果下一个字符，输入C,则会进入状态4，如果输入字符A，则会进入状态1，依次类推，如果既非A，又非C，则状态变为0
所谓的状态机，在数据结构上表现，就是一个表格，即状态转移表，列代表了模式串每个字符，行代表了每个字符在对应位置要进行转移的状态，如下：
上图为模式串 ACACAGA的状态转移表（T代表其他非ACG的字符）
具体怎么样呢，比如，有一个字符串 B A A C C A C A C A C A G A G
依次输入每个字符进入状态机，对应的状态就为
| 字符 | B | A | A | C | C | A | C | A | C | A | C | A | G | A | G |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 状态 | 0 | 1 | 1 | 2 | 0 | 1 | 2 | 3 | 4 | 5 | 4 | 5 | 6 | 7 | 0 |
明显，状态7的位置（包括）前7位，就是找到匹配的字符串。
利用生成好的状态机进行字符串匹配，很简单。复杂的是如何生成该状态机
des[N] 表示目标串，例如ABACAABABAACK，pat[M] 表示模式串，如ABAB, des[i...j] 表示 des[] 中从i到j的子串, pat[i...j]的定义类似，数组下标从1开始
根据有限状态自动机的定义，长度为M的pat[M],状态为分别为0，1，2，，，，，M-2，M-1,M,即共有M+1种状态。
假设模式串中不同的字符个数为 L（即模式串内总共非重复字符种类个数，如ABAB内的A，B，共2个字符）
则状态转移表为table[L] [M+1]
当字符串匹配处于某个状态s后，下一个可能的字符输入ch有L+1种可能。根据确定有限状态机的定义，在某一个状态下，任何一个输入都可以进入下一个确定状态
则此时有三种可能
1.pat[s+1]=ch,则ch下的状态为s+1
2.ch 不属于L种类内，则ch状态为0
3.ch剩余L种类，但是pat[s+1] != ch,则需要求出字符串 pat[1…s]+ch=str 的最长相同前后缀子串pat[1…k]，则k就为ch下的状态
前1，2种很容易理解
关键是情况3，为什么k就为ch的状态
1.假设i为ch的状态，且i>k,那么，pat[1…i]必定为str的前后缀，则与pat[i…k]为str的最长前后缀假设冲突，因为pat[1…i]的长度已经超过pat[1…k]的长度了，假设不成立
2.假设i为ch的状态，且i<k，确实，这样设定没有什么不合理的地方，但是有个问题，当下一个输入ch+1与pat[k+1]匹配时，可能i会漏掉这种可能，因为ch+1可能与pat[i+1]字符不同，但是如果此时i=k,则不会漏掉这种情况。因此，这里也不能采用
综合1，2，就需要求出str的最长相同前后缀子串pat[1…k]，k作为ch下的状态
利用这三种情况，自动机字符串匹配代码实现代码如下源码