串的模式匹配

空空 Voemp2023-12-112025-02-25

一、什么是串的模式匹配

主串 S = ababcabcacbab
模式串 T = abcac

目的：在主串中找到一个与模式串相同的子串，确定其位置

二、串的模式匹配算法

1.BF 算法

(1) 概念

BF 算法也叫暴力匹配算法。顾名思义，即从主串的第一位开始，每一位与模式串进行匹配，如遇到不匹配的字符，则从主串的第二位开始，后面每一位与模式串进行匹配，以此类推，直到找到与模式串完全匹配的子串并输出子串的头部地址，如主串中不存在与模式串相同的子串，则直到查找到主串最后一位之后退出算法。

下图是例子：

(2) 缺点

比较指针 i 每次都会回溯，效率太低，BF 算法最坏时间复杂度为 O (nm)，其中 n 和 m 分别为主串和模式串的长度。

2.KMP 算法

(1) 引入

想要避免指针 i 的回溯，让每次匹配失败后，指针 i 不动，那么我们就要通过特定的计算，操控模式串的位置。如果已匹配相等的前缀序列中有某个后缀正好是模式串的前缀，那么就可以将模式串向后滑动到与这些相等字符对齐的位置，主串 i 指针无须回溯，并继续从该位置开始进行比较。而模式串向后滑动位数的计算仅与模式本身的结构有关，与主串无关。

KMP 算法的时间复杂度为 O (n+m)

(2) 字符串的前缀、后缀和部分匹配值

前缀指除最后一个字符以外，字符串的所有头部子串。
后缀指除第一个字符外，字符串的所有尾部子串。
部分匹配值则为字符串的前缀和后缀的最大公共前后缀长度。
eg：
- 串：abca
- 前缀：a、ab、abc
- 后缀：a、ca、bca
- 部分匹配值：1

(3)next[j]

我们通过建立一个名为 next [j] 的数组来存放模式串中每一个字符遇到与主串不匹配时，指针 j 应该回到的位置。

next [j] 的计算方式：

第一个是 0，第二个是 1（固定）
max {n 个前缀 = n 个后缀}，n 即为部分匹配值，写 n+1
前缀≠后缀，写 1

eg：

j	1	2	3	4	5	6	7
模式串 T	a	b	c	a	b	c	b
next[j]	0	1	1	1	2	3	4

(4)nextval[j]

前面定义的 next [j] 数组在某些情况下尚有缺陷，还可以进一步优化，如模式串’aaaab’和主串’aaabaaaab’进行匹配时：

主串 S	a	a	a	b	a
模式串 T	a	a	a	a	b
j	1	2	3	4	5
next[j]	0	1	2	3	4
nextval[j]	0	0	0	0	4

显然后面 3 次用一个和 T [4] 相同的字符跟 S [4] 比较毫无意义，必然失配。改进过的 KMP 算法，在计算出 next 值的同时，如果 a 位字符与它 next 值指向的 b 位字符相等，则该 a 位的 nextval 就指向 b 位的 nextval 值，如果不等，则该 a 位的 nextval 值就是它自己 a 位的 next 的值。

nextval [j] 的计算方式：