字符串匹配（二）有限自动机

有限自动机，通过对文本字符串T进行扫描，找出模式P的所有出现位置。它们只对每个文本字符检查一次，并且检查每个文本字符时所用的时间为常数。因此，在模式预处理完成并建立好自动机后进行匹配所需要的时间为$\Theta(n)$。预处理的时间为$O(m|\Sigma|)$

有限自动机开始于状态$q_{0}$，每次读入输入字符串的一个字符。如果有限自动机在状态q时读入了字符$a$，则它从状态$q$变为状态$\delta(q,a)$。每当当前状态$q$属于$A$时，就说自动机$M$接受了迄今为止所读入的字符串。

状态1（被涂黑）是唯一的接受状态。

$\delta(0,a)=1$,$\delta(1,b)=0$,$\delta(0,a)=1$,$\delta(1,a)=0$,$\delta(0,a)=1$。因而接受abaaa这个输入。

有限自动机M引入一个状态函数$\phi$，称为终态函数，它是从$\Sigma^{*}$到Q的函数，满足$\phi(w)$是M在扫描字符串w后终止时的状态。当且仅当$\phi(w)\in A$时，M接受字符串w。（$A\in Q$是一个特殊的接受状态集合。利用状态转移函数递归定义$\phi$：

$\phi(\epsilon)=q_{0}$

$\phi(wa)=\delta(\phi(w),a),w\in\Sigma^{*},a \in\Sigma$

假设文本长度为n，模式长度为m，则自动机将会有0,1，...，m这么多种状态，并且初始状态为0。在从文本从左到右扫描时，对于每一个字符a，根据自动机当前的状态还有a的值可以找出自动机的下一个状态，这样一直扫描下去，并且一定自动机状态值变为m的时候我们就可以认为成功进行了一次匹配。

后缀函数

定义一个辅助函数$sigma$，函数$\sigma$是一个从$\Sigma^{*}$到$\{0,1,...,m\}$的映射。

举例解释：对于模式$P=ab$，有$\sigma(\epsilon)=0$,$\sigma(ccaca)=1$,$\sigma(ccab)=2$。对于一个长度为$m$的模式P，$\sigma(x)=m$当且仅当$x\in P$。

有限自动机定理：

• 状态集合Q为$\{0,1,...,m\}$。开始状态$q_{0}$是0状态，并且只有状态m是唯一被接受的状态。
• 对于任意的状态$q$和字符$a$，转移状态函数$delta$定义为

$\delta(q,a)=\sigma(P_{q}a)$,

也就是记录已得到的与模式P匹配的文本字符串T的最大前串。

假设现在文本和模式只有三种字符a,b,c，已经文本T为"abababaca",模式P为"ababaca"，根据模式P建立自动机如下图(b)（先不管实现细节）：

如图(c),对照自动机转换图(b),一个个的扫描文本字符，扫描前状态值初始化为0，这样在i = 9的时候状态值刚好变成7 = m，所以完成一个匹配。

建立模式P = "ababaca"的有限自动机。首先需要明白一点，如果当前的状态值为k，其实说明当前文本的后缀与模式的前缀的最大匹配长度为k，这时读进下一个文本字符，即使该字符匹配，状态值最多变成k + 1.假设当前状态值为5，说明文本当前位置的最后5位为"ababa"，等于模式的前5位。

如果下一位文本字符是"c"，则状态值就可以更新为6.如果下一位是"a"，这时我们需要重新找到文本后缀与模式前缀的最大匹配长度。简单的寻找方法可以是令k = 6(状态值最大的情况），判断文本后k位与模式前k位是否相等，不等的话就k = k - 1继续找。由于刚才文本后5位"ababa"其实就是模式的前5位，所以实际上构建自动机时不需要用到文本。这样可以找到这种情况状态值将变为1(只有a一位相等）。同理可以算出下一位是"b"时状态值该变为4（模式前4位"abab"等于"ababab"的后缀）。请对照图(c)进行理解。