串的模式匹配

一、什么是串的模式匹配

• 主串 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]的计算方式：

1. 第一个是0，第二个是1（固定）
2. max{n个前缀=n个后缀}，n即为部分匹配值，写n+1
3. 前缀≠后缀，写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	a	a	a	b
模式串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]的计算方式：

1. 第一位写0
2. 第二位字符若与第一位相同写0，不同写1
3. 从第三位开始，根据当前位的next值指路，找到next对应位置的字符
   • 相同：next字符的nextval值
   • 不同：当前字符的next值

eg：

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