使用有限自动机进行字符串匹配

字符串匹配自动机是在字符串匹配算法中使用的非常有用的工具。它仅对文本中的每个字符进行一次检查, 并报告所有有效的O（n）时间偏移。字符串匹配的目的是在较大的文本主体（句子, 段落, 书等）中找到特定文本模式的位置。

有限自动机

有限自动机M为5元组（Q, q0, A, ∑δ）, 其中

• Q是一组有限的状态
• q0∈Q是开始状态,
• ⊆Q是一组显着的接受状态,
• ∑是一个有限的输入字母,
• δ是从Q x ∑到Q的函数, 称为M的跃迁函数。

有限自动机从状态q0开始, 一次读取一个输入字符串的字符。如果自动机处于状态q并读取输入字符a, 则它会从状态q移到状态δ（q, a）。每当其当前状态q是A的成员时, 机器M都会接受到目前为止已读取的字符串。不允许的输入将被拒绝。

有限自动机M诱发一个称为最终状态函数的函数from, 从∑ *到Q, 使得∅（w）是扫描字符串w之后M最终进入的状态。因此, 当且仅当∅（w）∈A时, M才接受字符串w。

函数f定义为

∅ (∈)=q0
∅ (wa) = δ ((∅ (w), a) for w ∈ ∑*, a∈ ∑)

FINITE- AUTOMATON-MATCHER (T, δ, m), 1. n ← length [T]
 2. q ← 0
 3. for i ← 1 to n
 4. do q ← δ (q, T[i]) 
 5. If q =m
 6. then s←i-m
 7. print "Pattern occurs with shift s" s

FINITE-AUTOMATON-MATCHER的主要循环结构表明, 它在长度为n的文本字符串上的运行时间为O（n）。

计算转移函数：以下过程根据给定模式P [1 …… m]计算转移函数δ

COMPUTE-TRANSITION-FUNCTION (P, ∑)
 1. m ← length [P]
 2. for q ← 0 to m
 3. do for each character a ∈ ∑*
 4. do k ← min (m+1, q+2)
 5. repeat k←k-1
 6. Until
 7. δ(q, a)←k
 8. Return δ

示例：假设一个有限自动机接受偶数个a, 其中∑ = {a, b, c}

解：

q0是初始状态。