数据结构-串

模式匹配

$n=|T|,m=|P|,s=|\Sigma |$ 暴力算法：最好 $\Omega (n)$，最坏 $O(n\cdot m)$

KMP

建立一张表，在比对失败后不再从头开始比对，而是从模式串中某一字符开始比对，且使得模式串的前缀已经匹配。

构造 next 表

显然 $next[0]=-1$，通过递推构造剩余的 next 表：

• 取 $t=next[j]$
• 若 $P[j]=P[t]$，有 $next[j+1]=t+1$
• 否则令 $t=next[t]$，继续迭代

均摊分析

Aggregate

令 $k=2\cdot i-j$， 若匹配，$k$ 正好加一 若不匹配，查跳转表，$j$ 必然减少，$k$ 至少加一 因此 $k$ 单调递增，是操作次数的上界。 终态 $k\le 2n-1$，因此时间复杂度为 $O(n)$

Accounting

若匹配，则记账至当前元素，每个元素必然只出现一次这种记账 若不匹配，则记账至当前匹配的首元素，由于匹配的首元素必然递增，每个元素必然只出现一次这种记账。 因此时间复杂度为 $O(n)$

改进

若出现失配，在跳转后应该希望当前元素和跳转后位于当前位置的元素不同，否则又会导致失配 只需在构造 next 表时保证 $P[j+1]\ne P[t+1]$

• 取 $t=next[j]$
• 若 $P[j]\ne P[t]$，取 $t=next[t]$，继续迭代
• 否则若 $P[j+1]\ne P[t+1]$，令 $next[j+1]=t+1$
• 否则令 $next[j+1]=next[t+1]$，由数学归纳法，此时的 $next[t+1]$ 必然可以保证 $P[j+1]\ne P[next[t+1]]$

总结

字符集越小，优势越明显，否则与暴力性能相近 最坏和平均时间复杂度均为 $O(n+m)$

BM

BC 策略

每次匹配时从右向左遍历 P，遇到不匹配的字符，借助 bc 表快速右移到第一个使得当前字符匹配的位置，再重新从右向左匹配。

bc 表的构造

表长为 $s$，每个元素代表 $P$ 中对应字符最靠后的位置 使用画家算法，初始化为 -1，从前向后遍历字符串并更新表

性能

• 最好情况：若 $P$ 中不包含失配的字符，则可以直接跳过整个串，$O(n/m)$
• 最坏情况：匹配到迭代中的最后一个字符才失配，且匹配串中包含了全部字符，则只有每次匹配全串后才能右移一步，退化为暴力算法，$O(nm)$
• 字符集越小，越容易出现最坏情况 仅仅利用了失配的信息，能否利用上已匹配后缀的信息？

GS 策略

匹配时从后向前遍历 $P$，遇到第一次失配时，可以知道此时 $P$ 的后缀是匹配的，跳转到最靠后的与这段后缀相同，且当前待匹配字符不同的 $P$ 的中缀。若不存在这样的中缀，则跳转到与这段后缀匹配的最长前缀（可能为空，此时等同于跳转到开头）。 gs 表中保存的是右移字符数 如何构造 gs 表？

ss 表

定义 ss 表，对于每一元素，ss 的值为以该元素为末尾的最长的与 $P$ 的后缀匹配的中缀的长度。

ss 表的构造

问题转化为如何构造 ss 表。暴力算法时间复杂度为 $O(m^2)$ 从后向前扫描，维护一个匹配区间 $[lo,hi]$，满足该区间与后缀可以匹配。 首先 ss[m-1] = m，接着从倒数第二个字符开始从右向左扫描。 对于当前元素 $j$，总有 $j\le hi$

• 若 $j\in [lo,hi]$，此时 $j$ 的局部和 $m-hi+j$ 相同（匹配的后缀内）且 $j-lo>ss[m-hi+j]$，可以直接套用之前的计算结果，$ss[j]=ss[m-hi+j-1]$
• 否则更新 $hi=j$ ，从 $lo$ 开始继续逐一匹配，更新 $lo$
  • 对于 $j\in [lo,hi]$ 的情况，当且仅当 $ss[m-hi+j]\ge j-lo$ 时进入该分支，此时保证了从 $m-hi+lo$ 到 $m-hi+j$ 可以与后缀匹配。因此可以直接将 $hi$ 更新为 $j$ 并从 $lo$ 开始进行匹配。

由 ss 表构造 gs 表

可以由 ss 表在 $O(m)$ 内构造出 gs 表：

• 若 $ss[j]=j+1$，即整个前缀可以与后缀匹配，匹配的后缀的第一个元素的秩为 $m-j-1$，则对于任意 $i<m-j-1$，$m-j-1$ 是 $gs[i]$ 的一个候选
• 若 $ss[j]\le j$，匹配的后缀的第一个元素的秩为 $m-ss[j]-1$，中缀的第一个元素的秩为 $j-ss[j]$，二者间隔 $m-j-1$，因此此时 $m-j-1$ 是 $gs[m-ss[j]-1]$ 的一个候选 从后向前做一次遍历，检查所有 $ss[j]==j+1$ 的情况，并将 $m-j-1$ 赋值给上次赋值结束位置到 $j$ 的元素（因为前一次的赋值更小）。

KMP vs BM

Karp-Rabin 算法

将串视为一个 $s$ 进制数，通过散列映射到一个较小的空间中即可得到一个串的“指纹”。 $O(1)$ 时间内即可从上一指纹得到下一指纹。

键树