有限自动机,通过对文本字符串T进行扫描,找出模式P的所有出现位置。它们只对每个文本字符检查一次,并且检查每个文本字符时所用的时间为常数。因此,在模式预处理完成并建立好自动机后进行匹配所需要的时间为。预处理的时间为
有限自动机开始于状态,每次读入输入字符串的一个字符。如果有限自动机在状态q时读入了字符
,则它从状态
变为状态
。每当当前状态
属于
时,就说自动机
接受了迄今为止所读入的字符串。
状态1(被涂黑)是唯一的接受状态。
,
,
,
,
。因而接受abaaa这个输入。
有限自动机M引入一个状态函数,称为终态函数,它是从
到Q的函数,满足
是M在扫描字符串w后终止时的状态。当且仅当
时,M接受字符串w。(
是一个特殊的接受状态集合。利用状态转移函数递归定义
:
假设文本长度为n,模式长度为m,则自动机将会有0,1,...,m这么多种状态,并且初始状态为0。在从文本从左到右扫描时,对于每一个字符a,根据自动机当前的状态还有a的值可以找出自动机的下一个状态,这样一直扫描下去,并且一定自动机状态值变为m的时候我们就可以认为成功进行了一次匹配。
后缀函数
定义一个辅助函数,函数
是一个从
到
的映射。
举例解释:对于模式,有
,
,
。对于一个长度为
的模式P,
当且仅当
。
有限自动机定理:
- 状态集合Q为
。开始状态
是0状态,并且只有状态m是唯一被接受的状态。
- 对于任意的状态
和字符
,转移状态函数
定义为
,
也就是记录已得到的与模式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)进行理解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Compute-Transition-Function(P, ∑) { m = P.length; for q=0 to m { for each character A∈∑ { k = min(m,q+1); while(Pk is not a prefix of PqA) k--; δ(q,a)=k; } } } |