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

字符串匹配自动机是在字符串匹配算法中使用的非常有用的工具。它仅对文本中的每个字符进行一次检查, 并报告所有有效的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}