KMP

1. 简介

KMP 算法是一种优秀的字符串模式匹配算法,相对于暴力匹配方法来说,其改进在于:每当一趟匹配过程出现字符比较不相等时,不需回溯主串的 ii 指针,而是利用已经得到的「部分匹配」的结果将模式串向右「滑动」尽可能远的一段距离后(即回溯模式串的 jj 指针),继续进行比较。

2. 实现

  • 设模式串为 p1p2pmp_1 p_2 \cdots p_m,主串为 s1s2sns_1 s_2 \cdots s_n

  • 定义失配数组 next[j]next[j] 表示当模式串中第 jj 个字符与主串中相应字符失配时,在模式串中需要重新和主串中该字符进行比较的模式串字符的位置。

  1. 假设从主串第 pospos 个字符开始和模式串匹配,此时主串中第 i(posi)i(pos \leq i) 个字符和模式串的第 jj 个字符比较,且 sipjs_i \ne p_j,说明从主串第 pospos 个字符开始匹配无法找到模式串子串,因此需要将 pospos 向右「滑动」(即增大主串开始匹配字符的位置)。
  2. 而增大主串开始匹配字符的位置可以通过将模式串向右「滑动」实现。如果此时存在最大的 kk 使得 p0pk1=pjkpj1 p_0 \cdots p_{k-1} = p_{j-k} \cdots p_{j-1} pkpj p_k \ne p_j ,则可以将模式串向右「滑动」使得模式串第 kk 个字符对应到第 jj 个字符,即模式串整体向右滑动了 jkj-k 个字符。
  • k=max{u0<u<jp0pu1=pjupj1} k = max\{u | 0 \lt u \lt j \bigwedge p_0 \cdots p_{u-1} = p_{j-u} \cdots p_{j-1}\} ,则失配数组的计算公式如下:

next[j]={1j=0kif pkpjnext[k]if pk=pj\begin{array}{c} next[j] = \begin{cases} -1 & j = 0 \\ k & if \ p_{k} \ne p_{j} \\ next[k] & if \ p_{k} = p_{j} \end{cases} \end{array}

计算失配数组时间复杂度 O(m)O(m),主串与模式串匹配时间复杂度 O(n)O(n),故 KMP 算法总的时间复杂度为 O(n+m)O(n+m)

3. 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

#ifndef _KMP_
#define _KMP_
#define ll int
#define MAXN 1000005
#define MAXM 1000005

// KMP 算法
struct KMP {
// 失配数组
// next[j] 表示当模式中第 j 个字符与主串字符失配时
// 模式串中失配位置需要滑动到的位置
ll next[MAXM];
vector <ll> match;
KMP() {}
// 计算失配数组
void getNext(char *pattern, ll m) {
// pattern 模式串
next[0] = -1;
ll i = 0, j = -1;
while(i < m) {
if(!(~j) || pattern[i] == pattern[j]) {
++i, ++j;
if(pattern[i] != pattern[j]) next[i] = j;
else next[i] = next[j];
} else {
j = next[j];
}
}
}
// 计算模式串在主串中第 pos 个字符后出现首个匹配的首位置
ll getIndex(ll pos, char *main, ll n, char *pattern, ll m) {
ll i = pos, j = 0;
while(i < n && j < m) {
if(!(~j) || main[i] == pattern[j]) {
++i, ++j;
} else {
j = next[j];
}
}
if(j < m) {
return -1;
}
return i - m;
}
// 计算模式串在主串中所有匹配的首位置
void getIndexs(char *main, ll n, char *pattern, ll m) {
ll i = 0, j = 0;
while(i < n) {
if(!(~j) || main[i] == pattern[j]) {
++i, ++j;
if(j == m) {
j = next[j];
match.push_back(i-m);
}
} else {
j = next[j];
}
}
}
};
#endif

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!