数据结构｜串的模式匹配（朴素匹配+KMP+nextval）

说明：本文下标从 1 开始

1.基本概念

模式匹配是指在主串中查找与模式串（待搜索的字符串）完全相同的子串，并返回其首次出现的位置

子串与模式串的区别：

• 子串：是主串的一部分，在主串中一定存在
• 模式串：待搜索的字符串，在主串中不一定存在

2.朴素模式匹配算法：

朴素模式匹配算法的时间复杂度O(mn)

核心思想

逐个对比主串和模式串的字符，如果字符匹配不成功，模式串回溯到第一个位置，主串回溯到本轮起始位置的下一个位置重新匹配，直到找到主串中与模式串完全相同的子串，返回子串起始位置

字符匹配失败时

• i = i - (j - 1) + 1 = i - j + 2
• j = 1

匹配成功

返回模式串在主串中首次出现的位置：return i - T.length;

3.KMP算法

KMP算法是对朴素模式匹配算法的优化

核心思想

匹配失败时i不回退，仅通过预处理得到的next数组调整 j 的位置，避免了重复字符的比较，从而将时间复杂度从O(mn)优化为O(m + n)

时间复杂度

• 预处理next数组 O(m)
• 匹配 O(n)
• 总时间复杂度 O(m + n)

4.next数组的计算

next[j]的含义

当模式串的第j个字符失配时，下一轮应从模式串的next[j]位置开始比较

规则

• next[1] = 0，next[2] = 1
• 从模式串的第三个字符开始，next数组的值是模式串中当前字符之前的串的最长公共前后缀的长度+1

例1：T = ababaa

下标	1	2	3	4	5	6
next	0	1	1	2	3	4

next[1] = 0, next[2] = 1
从模式串的第3个字符 a 开始：

• 第3个字符 a 前面是 “ab”，没有公共前后缀，所以next[3] = 0 + 1 = 1
• 第4个字符 b 前面是 “aba”，最长公共前后缀是 “a”，长度是1，所以next[4] = 1 + 1 = 2
• 第5个字符 a 前面是 ”abab”，最长公共前后缀是 “ab”，长度是2，所以next[5] = 2 + 1 = 3
• 第6个字符 a 前面是 “ababa”，最长公共前后缀是 “aba”，长度是3，所以next[6] = 3 + 1 = 4

例2：T = aaaab

下标	1	2	3	4	5
next	0	1	2	3	4

next[1] = 0, next[2] = 1
从模式串的第3个字符 a 开始

• 第3个字符 a 前面是 “aa”，最长公共前后缀是”a”，所以next[3] = 1 + 1 = 2
• 第4个字符 a 前面是 “aaa”，最长公共前后缀是 “aa”，长度是2，所以next[4] = 2 + 1 = 3
• 第5个字符 b 前面是 ”aaaa”，最长公共前后缀是 “aaa”，长度是3，所以next[5] = 3 + 1 = 4

[注意] 字符串的公共前后缀不包含字符串本身，如字符串”aaa”的公共前后缀是”aa”而不是”aaa”

5.KMP算法的进一步优化

在使用KMP算法进行模式匹配时，如果模式串j对应的字符和主串i对应字符不相等（失配）则将j移动至next[j]继续匹配，但j移动后指向的字符可能和移动前指向的字符相同，此时出现了重复的比较并且一定会失配，所以可以使用nextval数组优化这种重复比较的情况

nextval数组的计算

• nextval[1] = 0
• 从第 2 个字符开始
  • 当模式串中j对应的字符和next[j]对应的字符相等时，nextval[j]的值等于next[j]的nextval值，即 nextval[j] = nextval[next[j]]
  • 当模式串中 j 对应的字符和next[j]对应的字符不相等时，nextval[j]的值等于next[j]的值，即 nextval[j] = next[j]

例1：T = ababaa

下标	1	2	3	4	5	6
next	0	1	1	2	3	4
nextval	0	1	0	1	0	4

nextval[1] = 0
从模式串的第2个字符 a 开始：

• next[2] = 1，T.ch[1] = a，T.ch[2] = b，字符不相等 -> nextval[2] = next[2] = 1
• next[3] = 1，T.ch[1] = a，T.ch[3] = a，字符相等 -> nextval[3] = nextval[next[3]] = 0
• next[4] = 2，T.ch[2] = b，T.ch[4] = b，字符相等 -> nextval[4] = nextval[next[4]] = 1
• next[5] = 3，T.ch[3] = a，T.ch[5] = a，字符相等 -> nextval[5] = nextval[next[5]] = 0
• next[6] = 4，T.ch[4] = b，T.ch[6] = a，字符不相等 -> nextval[6] = next[6] = 4

例2：T = aaaab

下标	1	2	3	4	5
next	0	1	2	3	4
nextval	0	0	0	0	4

nextval[1] = 0
从模式串的第2个字符 a 开始：

• next[2] = 1，T.ch[1] = a，T.ch[2] = a，字符相等 -> nextval[2] = nextval[next[2]] = 0
• next[3] = 1，T.ch[1] = a，T.ch[3] = a，字符相等 -> nextval[3] = nextval[next[3]] = 0
• next[4] = 2，T.ch[2] = a，T.ch[4] = a，字符相等 -> nextval[4] = nextval[next[4]] = 0
• next[5] = 3，T.ch[3] = a，T.ch[5] = b，字符不相等 -> nextval[5] = next[5] = 4