alg: 字符串匹配算法

这是以 alg 作为标题前缀的数据结构与算法系列。
本系列的更新策略：直接更新内容，不标出更新的年月日。

本系列的写作参考了诸多来源，一个重要来源是清华大学数据结构课程（邓俊辉课堂的）讲义和《数据结构（C++语言版）》的内容，有些段落可能文字复制比 / 伪代码复制比较高，但不保证相关部分与上述来源完全一致。如果你想要系统性地初学数据结构与算法，推荐从上述两个材料入手，它们可以从这个链接获取。

本系列的思维方法

设计算法和证明算法的正确性是两回事：

设计算法的一般模式是自顶向下，设计一个算法框架，并递归地实现上一级函数用到的函数。在实现函数的过程中，只需要口头 / 能用自然语言解释每个变量的含义、每一步在干什么就可以了。
证明一个算法是正确的远比构造一个算法复杂琐碎。

在编程竞赛 / 现场编程等场景中，你需要短时间内给出一个事实上工作的代码。因此，在这类场景中，需要按照“设计”的模式编程。

下面仅仅列出算法，默认不给出证明。

字符串匹配问题

我们希望找到模式串B在文档串A中的所有出现位置。设文档串A长度为n，模式串B长度为m。

一个直观的思路就是，将模式串B与文本串A的“左端”对齐，尝试匹配，如果不匹配（后称失配），让模式串相对文本串右移一定的位置，记为di，再次尝试匹配，直到模式串超出了文本串的右端。

使用蛮力算法，模式串每次右移1 (di=1)，则复杂度为O(mn)

利用已经匹配的经验，指导模式串位移 di，能够降低字符串匹配算法的复杂度。在这个大思路下，在每个位置尝试匹配的流程可以从左到右或者从右到左，两者分别对应KMP和BM算法。

从左到右匹配模式串：KMP 算法

设在文本串的位置 i 失配，设已经匹配的部分有 j 个字符，即 A[i, i+j) = B[0, j), A[i+j] != B[j]。文本串该右移多少呢？（i += di, di = ?）

要求是不能错过任意可能的匹配

di = min_{k>0} { A[i+k, i+j) == B[0, j-k) }
   = min_{k>0} { B[k, j) == B[0, j-k) }
   (t := j-k)
   = j - max_{0<=t<j} { B[0, t) == B[j-t, j) }
  := j - next[j]

这个可以看出这个位移只和 j 和字符串B有关，可以事先存储在一个数列/表中，称为 next 表。例如，“MAMAMMIA”的 next 表就是 [-1, 0, 0, 1, 2, 3, 1, 0]，next[0]=-1 保证了 j=0 没有字符匹配时模式串右移一位。

构造 next 表

可以递推地构造 next 表：

next = [-1]*m
t = -1
j = 0
while j < m-1
  if t < 0 or B[j]==B[t]
    j, t = j+1, t+1
    N[j] = t
  else
    t = next[t]

其中，t 是 B[0, j) 最长的匹配前后缀长度。或者说，是已经匹配的字符数量。

每次循环，加入字符 B[j] 。如果加入后缀的下一个字符 B[j] 正好和前缀 B[0, t) 的下一个字符 B[t] 一致，那么匹配的字符数量多了一个。否则，降低预期，寻找更短的前后缀匹配，它恰好为 next[t]。

匹配文本串

应用 next 表做匹配时，每次移动之后不一定需要从模式串的左端开始重新匹配，而是可以利用上次的部分结果。

i, j = 0, 0
while (j < m and i < n)
  if j < 0 or A[i]==B[j]
    i, j = i+1, j+1
  else
    j = next[j]
return i-j

循环的不变量是 A[i-j, i)==B[0, j)。模式串左端对准的位置是 i-j

如果下一个字符匹配，则已经匹配的长度加一，模式串左端对准的位置不变。否则，模式串向右移动 j – next[j] 步，或者说保留 next[j] 个匹配的字符。

复杂度分析

构造 next 表的算法中，每个循环内，要么 j, t 各加一，要么 t 至少减一（因为 next[t] < t）。因此 2j-t 每个循环至少增加 1，循环最多执行了 2(m-1)-1 次，构造 next 表的复杂度是 O(m) 的。

同理，在匹配文本串的算法中，每个循环内 2i-j 至少增加 1，匹配的复杂度是 O(m+n) 的。

从右到左匹配模式串：BM 算法

BM 算法的核心框架是从右到左匹配，算法设计如下

i = 0
while n >= i + m
  j = m - 1
  while B[j]==A[i+j]
    j = j - 1
    if j < 0
      break # matched
  if j < 0 # matched
    return i
  else
    i = i + max(gs[j], j - bc[A[i+j]])

其中，i 是模式串左端对准的位置，j 是模式串中正在用于比对的（或失配的）位置。每次失配发生时，模式串右移的距离由“好后缀”（Good Suffix, gs）和”坏字符”（Bad Character, gc）两个策略决定，两个策略都可以排除 i 之后紧接着的一系列一定不能匹配的位置。

坏字符策略

如果文本串中需要匹配的字符 A[i+j] 在模式串 B 中出现的位置都很靠左，就可能可以大量右移模式串 B。依据这个思路，记录字母表中每个字母 c 在 B 中出现的最靠右的位置的指标为 bc[c]。这样，满足对所有的 k > bc[c]，都有 B[k] != c 。不难看出，至少应当右移 j – bc[A[i+j]] 。

好后缀策略

由于后缀已经匹配 B(j, m) == A(i+j, i+m)，模式串右移 s 后能够匹配的必要条件是 B(j, m)==B(j-s, m-s)。对于每个 j，需要找出满足必要条件的最小 s，即 gs[j] 。

gs 表的构造较为复杂，在这里略去。

复杂度

经过简单的改进，该算法的复杂度可以为 O(n+m)。