[算法] 字符串匹配

问题定义

文本T[1..n] 模式P[1..m]
找到所有的偏移s(0<=s<=n-m)，使得是的后缀
前缀符号 后缀符号
后缀重叠引理 前缀和后缀关系为传递关系

运行时间

运行时间 = 预处理时间 + 匹配时间

朴素匹配算法

如果模式中所有字符都不相同，运行时间可达

Rabin Karp算法

将和预处理为以d为基数表示的数字：
P的预处理时间为
T的预处理时间使用下式计算为:


如果说明该偏移s为伪命中点，可进行循环检测P[1..m] = T[s+1..s+m]，最坏匹配时间，期望匹配时间

有限自动机匹配

符号定义

有限自动机
后缀函数是能作为x的后缀的P的最长前缀长度

预处理阶段

构造模式串的字符串匹配自动机
状态Q={1,2..m}，为0，状态m为唯一接受状态(但m也需要求状态转移函数)

• 计算转移函数

Compute-transition-function
m = P.length
  for q = 0 to m
    for each character a in \Sigma
     k = min(m, q+1)
     while P_k 不是P_q+a的后缀
        k--
     \delta(q,a) = k
return \delta

时间复杂度

• 利用kmp中的π求此处的转移函数可以将时间复杂度降低为​
  因为，所以有，而表示能构成真后缀的P的最长前缀长度，表示能构成的后缀的P的最长前缀长度，因此，。同时如果 且那么直接等于即可，综合可得，如果 或 那么​。根据上式利用前缀函数​只需m次循环便可计算得到转移函数，时间复杂度为​：

COMPUTE-TRANSITION-FUNCTION(P, Σ)
    π = COMPUTE-PREFIX-FUNCTION(P)
    for a ∈ Σ 
        δ(0, a) = 0
    δ(0, P[1]) = 1
    for a ∈ Σ 
        for q = 1 to m 
            if q == m or P[q + 1] != a 
                δ(q, a) = δ(π[q], a)
            else
                δ(q, a) = q + 1

匹配阶段

Finite-automation-matcher
n = T.length
q = 0
for i = 0 to n-1 
  q = \delta(q, T[i])
  if q == m
    print i - m

时间复杂度

Knuth Morris Pratt算法

符号定义

前缀函数 是能构成真后缀的P的最长前缀长度

预处理阶段

摊还分析，时间复杂度

Compute-prefix-function
m = P.length
pi[1] = 0
k = 0
  for q = 2 to m
    while k > 0 and P[k+1] != P[q]
      k = pi[k]
     if P[k+1] == P[q]
        k++
     pi[q] = k
return pi

注意！前缀函数所要求的真后缀是指k必须满足小于q，例如模式串首个字符的后缀本身必定也是它的前缀，但k==q，因此此处赋值为0（字符串从1开始， 如果从0开始应赋值为-1）

匹配阶段

摊还分析，时间复杂度

KMP-Matcher
n = T.length
m = P.length
pi = Compute-prefix-function
q = 0
for i = 1 to n
  while q > 0 and P[q+1] != T[i]
    q = pi[q]
  if P[q+1] == T[i]
    q++
  if q == m
    print i - m
    q = pi[q]

Boyer Moore算法