比较朴素匹配与 KMP,掌握主串和模式串的匹配过程、next 数组的构造与失配回退,并理解 nextval 的优化目的。

# 一、模式匹配问题

给定主串 SS 和模式串 PP,模式匹配要找出 PP 在 SS 中首次出现的位置。若 ∣S∣=n|S|=n、∣P∣=m|P|=m,本文代码使用从 00 开始的数组下标;若模式串为空,约定返回 00。

若目标是返回所有匹配位置,而不是首次位置,成功后还需继续扫描;KMP 可令模式指针回退到匹配后缀对应的最长前后缀位置,再继续搜索。

# 二、朴素模式匹配

朴素算法依次尝试每个可能的起始位置。字符相同则继续比较;一旦失配,就将模式串右移一位,从新的起点重新比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int NaiveIndex(const char text[], int n, const char pattern[], int m) {
if (m == 0) {
return 0;
}
if (m > n) {
return -1;
}

for (int start = 0; start <= n - m; start++) {
int j = 0;
while (j < m && text[start + j] == pattern[j]) {
j++;
}
if (j == m) {
return start;
}
}
return -1;
}

设主串长度为 nn,模式串长度为 mm。最坏情况下,每个起始位置都比较接近 mm 个字符,因此时间复杂度为 O((n−m+1)m)O((n-m+1)m),常简写为 O(nm)O(nm);额外空间为 O(1)O(1)。

# 三、KMP 的核心思想

KMP(Knuth-Morris-Pratt)在失配时利用模式串自身的重复结构,避免把主串指针退回到刚才比较过的位置。已经匹配的模式串前缀中,若某个后缀也是前缀,就可以把模式串移到这个相同前后缀继续比较。

真前缀不等于整个串,真后缀也不等于整个串。对于串 P [0..j-1],其最长相等真前缀与真后缀的长度,就是失配后能够保留的已匹配字符数。

本文采用带哨兵的零基 next 约定:

  • next[0] = -1;
  • 对 j > 0,next [j] 表示在模式串下标 j 处失配后,模式串下一次应比较的下标;
  • 若主串当前字符与模式串下标 j 失配,就令 j = next [j];主串下标不回退。

有些教材把 next 定义成最长相等真前后缀的长度,或使用从 11 开始的下标。它们表示同一回退信息,但数组的首项、表中数值和代码不能混用。

# 四、构造 next 数组

设模式串为 ababaca,其字符下标从 00 开始。每一位失配时的回退位置如下。

下标 jj0123456
字符 P[j]P[j]ababaca
next[j]-1001230

例如在下标 j=5j=5 的字符 c 处失配,前面已匹配的 ababa 有最长相等真前后缀 aba,长度为 33,因此令模式下标回到 33,而不是回到 00。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BuildNext(const char pattern[], int m, int next[]) {
int i = 0;
int j = -1;
next[0] = -1;

while (i < m) {
if (j == -1 || pattern[i] == pattern[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}

next 数组至少需要 m+1m+1 个单元,因为构造过程会写入 next [m]。匹配过程中只在 j<mj<m 时访问模式串字符。

# 五、KMP 匹配过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int KMPIndex(const char text[], int n, const char pattern[], int m,
const int next[]) {
if (m == 0) {
return 0;
}

int i = 0;
int j = 0;
while (i < n && j < m) {
if (j == -1 || text[i] == pattern[j]) {
i++;
j++;
} else {
j = next[j];
}
}
return j == m ? i - m : -1;
}

以主串 ababababaca、模式串 ababaca 为例:

  1. 前五个字符 ababa 匹配,主串下标为 55、模式下标为 55。
  2. 主串字符 b 与模式字符 c 失配,令 j=next[5]=3j=next[5]=3,主串下标保持为 55。
  3. 此时主串和模式下标 33 都是字符 b,继续前进,不必重比前缀 aba。
  4. 后续再次失配时仍按 next 回退,最终从主串下标 44 找到模式串。

若 j=−1j=-1,表示已没有可保留的模式前缀,主串指针和模式指针同时向后移动一位。若 j=mj=m,说明完整模式串匹配成功,起始下标为 i−mi-m。

构造 next 和执行匹配都为线性扫描,时间复杂度为 O(n+m)O(n+m),辅助空间为 O(m)O(m)。

# 六、nextval 的改进

普通 next 有时会回退到一个与刚刚失配字符相同的模式字符,造成可预知的重复比较。修正后的 next 常记作 nextval:若 P [j] 与 P [next [j]] 相同,就继续采用 nextval [next [j]];否则仍采用 next [j]。

对模式串 ababaa,按上述零基约定:

下标 jj012345
字符 P[j]P[j]ababaa
next[j]-100123
nextval[j]-10-10-13

例如 j=4 时字符 a 失配,next [4]=2,而 P [4]=P [2]=a,继续比较仍会立即失配,因此修正为 nextval [2]=-1。nextval 只减少一些重复比较,不改变匹配结果;掌握 next 的含义和构造通常更重要。

计算 next 时,要先确认失配发生在模式串的哪一个下标、数组记录的是前后缀长度还是下一比较位置。只有在定义、下标和匹配代码完全一致时,表格才可直接使用。

# 七、考场检查清单

  1. 朴素算法在每次失配后把起点右移一位,最坏复杂度为 O(nm)O(nm)。
  2. KMP 失配时主串指针不回退,只调整模式串下标。
  3. next 保存的是失配后的回退信息;不同教材可能采用不同下标约定。
  4. 最长相等真前后缀不包含整个已匹配串本身。
  5. nextval 避免跳到一个会与当前失配字符重复比较的位置。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝