Introduction to Algorithm-05-String Matching

String Matching

问题描述：字符串匹配指的是在一个文本字符串中查找一个模式字符串的出现位置。这个问题在计算机科学中非常重要，尤其是在文本处理、搜索引擎和数据挖掘等领域。

Online Exact String Matching

在线匹配要求不能对文本进行预处理，并且必需精确匹配。前缀符号：$\sqsubset$，后缀：$\sqsupset$，定义前缀为$P[:k]$

Overlapping Lemma

Naive String Matching

算法：

1. 从文本的每个位置开始，检查模式是否匹配。
2. 如果匹配，则返回该位置；否则，继续检查下一个位置。

代码：

def naive_string_matching(text, pattern):
		n = len(text)
		m = len(pattern)
		for i in range(n - m + 1):
				match = True
				for j in range(m):
						if text[i + j] != pattern[j]:
								match = False
								break
				if match:
						return i  # 返回匹配位置
		return -1  # 未找到匹配

时间复杂度为$O((n-m+1)m)$，其中$n$是文本长度，$m$是模式长度。

如果得到pattern的信息，比如没有重复出现的字母，那么可以得到线性时间的算法。
如果发生失配的情况，那么前面失配的部分不可能再一次成功匹配，所有匹配只需要线性的$O(n)$时间

Rabin-Karp Algorithm

将文本的匹配转换为数值的匹配。

上述算法存在的问题为：

1. 对文本计算每一个子串对应的整数值
2. 对于较长的$m$的pattern，没有那么长的整数类型
3. 对于字母表大小有要求

解决方案为：

1. 使用滑动方法来计算文本对应的整数值
2. 使用hash函数来计算子串的hash值，比如使用取模的方法，如果hash值相同，则进行比较
3. 使用不同的进制，使得其匹配字母表的大小

复杂度分析：

• 计算hash值的复杂度为$O(m)$
• 计算文本的hash值的复杂度为$O(n)$
• 在最坏情况下算法复杂度为$\Theta((n-m+1)m)$，在平均情况下为$O(n) + O(m(v+\frac{n}{q}))$

Finitie automata

用于匹配的有限自动机，$M=\mathcal{M}$$\text{，}\text{是一个五元组}$$(Q, \Sigma, \delta, q_0, F)$

• $Q$是状态集合，$Q=\{ 0,1,2\dots m\}$
• $q_0=0$，$F = \{m\}$

定义后缀函数为：

目的为寻找对于一个pattern而言，寻找文本的后缀中最多能匹配多少pattern的前缀内容。定义上面的函数的目的是对于已经匹配的模式串$P[:k]$，如果在$k+1$的位置输入为$a$，那么需要$P[:k]a$的部分后缀是pattern的前缀。上面的转移规则将匹配的情况也一同表示。

上面构建的DFA的状态转移表的大小为$|\Sigma|\times m$，在构建状态转移函数的时候，使用的思路为对于目前的状态再输入一个字符，检查目前输入文本的后缀能匹配pattern前缀部分的长度。

上面是构造DFA的算法，对于模式串的每一个前缀都需要比较，每一个前缀比较的时间复杂度为对应串的平方复杂度，求和得复杂度为$O(m^3|\Sigma|)$，上面的算法可以进行优化。

KMP Algorithm

KMP算法的核心思想是避免不必要的比较，通过预处理模式字符串来构建一个部分匹配表（也称为前缀表），该表用于在匹配失败时确定下一个要比较的位置。

用前缀函数来表达这样的关系，表达在一个字符串的前缀中，其最大同时为前缀和后缀的字符串长度，形式化的表述为：

$$\pi[i]=\max\{k\mid k\leq i,\text{s.t.}p[1:k]=p[i-k+1:i]\}$$

设计原因是利用前缀匹配过程中成功的信息，对于模式串中成功匹配的部分，是否有前缀同时是后缀的情况。

上面给出计算next表的算法，注意第7行回退时，将$k$回退至$\pi(k)$。这是因为，考虑已经匹配的$P[:k]$和$P[q-k:q-1]$如果在$P[k+1]$和$P[q]$失配，考虑重新匹配的情况$P[:k^\prime+1]$和$P[q-k^\prime:q]$，必然有$P[:k^\prime]$和$P[q-k^\prime:q-1]$匹配。即重新找到匹配位置的必要条件为$P[:k]$中的最大前缀同时为后缀，所以回溯到$\pi(k)$，继续匹配。

对上面构建$next$表的过程进行复杂度分析，核心在于对6，7行运行时间的分析，注意到在运行过程中$k$是单调递增的且非负，且$k$的最大值为$m-1$，所以在整个过程中$k$最大为$m-1$，在构建$next$表过程中总有$k<q$，于是$k$最多减小$m-1$次，于是算法复杂度为$\Theta(m)$

在上面的KMP的$next$表构建的过程中仅使用了所谓的“成功的经验”，如果对应相等的前后缀串的后面一个字符仍然相等，此时没有再比较的必要。

If $P[q+1] \ne T[i]$, then if $P[\pi[q]+1] = P[q+1] \ne T[i]$, there is no need to compare $P[\pi[q]+1]$ with $T[i]$.

Boyer-Moore

字符串匹配 —— BM 算法 - 知乎

当从右侧向左侧开始比较时，可以得到更多的信息。

• 当发生失配时，当text中出现pattern中没有出现的字符时，直接将pattern的左端和text的下一个字符对齐。
• 当发生失配时，当text中的字符在pattern中出现时，直接将pattern中从右向左第一次出现该字符，和text中该字符对齐。
• 当发生失配时，将已经匹配的后缀部分与pattern中从右向左再一次出现已匹配部分对齐

将上面的观察总结为好字符和坏字符规则：

• 坏字符规则：当发生失配时，直接将pattern中从右向左第一次出现的该字符，和text中该字符对齐。（对于最右边的字符不考虑，因为已经比较过）

  $$bmBC[c] = \begin{cases} \min\{i\mid 1 \leq i\leq m-1 \wedge P[m-i]=c\} & \text{if } c \in P \\ m & \text{otherwise} \end{cases}$$

  数组中保存的是从右向左计数第一次发现字符的位置，发生跳跃的距离为$shift = bmBC[c]+ j-m$，即当前位置和第从右向左第一次出现位置的差。
• 好字符规则：当发生失配时，将已经匹配的后缀部分与pattern中从右向左再一次出现已匹配部分对齐
  考虑失配时，对于已经匹配的$P[m-k+1:m]$
  • 情况1：后缀$P[m-k+1:m]$在$pattern$中从右到左第一次出现，记为$P[i-k+1:i]$，并且$P[m-k]\neq P[i-k]$时（所谓失败的经验），将$P[i-k+1:i]$与$text$中对应部分对齐。
  • 情况2：找不到上面的情况时，寻找$pattern$串中的前缀和后缀$P[m-k+1:m]$的最大重叠部分，并且将$P[m-k+1:m]$与$text$中对应部分对齐。
    将上面的内容形式化表述为，其中$s$为$shift$即跳转长度

  $$\begin{aligned} &Cs(i,s): \text{for each k s.t. }i < k\leq m, P[k-s]=P[k] ~\text{or}~s\geq k \\ &Co(i,s): \text{if}~ s<i ~\text{then} P[i-s]\neq P[i]\\ &bmGs[i] = \min\{ s>0: Cs(i,s) \wedge Co(i,s) \} \end{aligned}$$

算法复杂度为$\Theta(m+|\Sigma|)$ ，在 $|\Sigma| \leq m$ 时，复杂度为$\Theta(m)$

对于好后缀的计算比较复杂

• 考虑重叠后缀函数Overlapping Suffix Function

  $$Osuff[i]= \max \{ k: P[i-k+1: i]= P[m-k+1:m]\}$$

  寻找从$i$位置向前和原pattern串中匹配的最长的后缀，可以使用暴力算法进行计算，朴素实现的时间复杂度为$O(m^2)$

• 使用反转后的pattern串使用Z算法进行计算，时间复杂度优化为$O(m)$Z 函数（扩展 KMP） - OI Wiki

  • 在上面的算法中，在5~10行中对应上面好后缀的情况2，由于好后缀要求最小性，所以从 $m-1$ 开始递减，并且要求$j \leq m-i$
  • 在第11~12行对应上面的好后缀情况为1时，由于$Osuff$的最大性，保证了$P[m-Osuff[i]]\neq P[i-Osuff[i]]$即为上面的好后缀的实现
  • 上面的算法过程中，注意到所有位置的赋值总是单调减小的，即满足上面$bmGs$的最小性质
  • 上面算法的时间复杂度为$\Theta(m)$

• 最终的BM算法的时间复杂度为$O(m+n)$，在最坏情况下为$O(mn)$