KMP算法

1 算法思想

1.1 思路

解决问题:当主串中第 i 个字符与模式中第 j 个字符失配(即比较不相等)时,主串中第 i 个字符(i 指针不回溯)应与模式中哪个字符再比较。

  1. next[j]next[j]:模式中第 j 个字符失配时,在模式中重新与主串比较的字符位置(最长公共前后缀长度+1,下标从 1 开始)

    \text { next }[j]=\left\{\begin{array}{ll} 0 & \text { 当 } j=1 \text { 时 } \\ \operatorname{Max}\left\{k \mid 1

  2. 计算next数组:仅取决于模式串本身而和相匹配的主串无关

    • 仿照kmp算法,如果p[j]!=p[next[j]]p[j] != p[next[j]],那么next[j+1]next[j+1]的可能次大值为next[next[j]]+1next[next[j]] + 1,依次类推即可高效求出next[j+1]next[j+1]
  3. 若在匹配过程中si=pjs_i=p_j,则 i 与 j 分别增 1;

  4. 否则,i 不变,j 退至 next[j] 的位置再比较;若 j 退到值为 0(即模式串的第一个字符失配),则从主串的下一个字符si+1s_{i+1}起与模式串重新开始匹配;

  5. 重复执行step3、step4,直至结束。

1.2 优化

修正next数组,next[j]=knext[j]=k,若模式中p[j]=p[k]p[j]=p[k],则next[j]=next[k]next[j] = next[k]

1.3 算法分析

  • 时间复杂度O(m+n)O(m+n)
  • 空间复杂度:next数组,O(m)O(m)

2 代码实现

2.1 C++

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
65
66
67
#include <iostream> 
typedef long long ll;
using namespace std;
// string、next数组下标从1开始
const int maxn = 1e4;
int next2[maxn];
int nextval[maxn];

// 计算next数组
void get_next(string p) {
int i = 1, j = 0;
next2[1] = 0;
while (i < p.size()) {
if (j == 0 || p[i] == p[j]) {
i++;
j++;
next2[i] = j;
} else {
j = next2[j];
}
}
}
//计算nextval数组
void get_nextval(string p) {
int i = 1, j = 0;
nextval[1] = 0;
while (i < p.size()) {
if (j == 0 || p[i] == p[j]) {
i++;
j++;
if (p[i] != p[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else {
j = nextval[j];
}
}
}
// KMP算法
int kmp(string s, string p) {
//get_next(p);//计算next数组
get_nextval(p);
int i = 0, j = 1;//主串从第i个字符之后匹配
while (i < s.size() && j < p.size()) {
if (j == 0 || s[i] == p[j]) {//模式串首字符失配或相同继续匹配
i++;
j++;
} else {//失配
j = nextval[j];
}
}
if (j >= p.size())//找到
return i - p.size() - 1;
else
return 0;
}
int main() {
std::ios::sync_with_stdio(false);
string s = " acabaabaabcacaabc", t = " abaabcac";
cout << kmp(s, t);
/*for (int i = 1; i < t.size(); i++) {
cout << next2[i] << endl;
}*/
return 0;
}

2.2 Java

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
65
66
67
68
69
class KMP {
private int maxn = 1000;
private int[] next = new int[maxn];
private int[] nextval = new int[maxn];

//构造函数
public KMP() {

}
//计算next数组
public void get_next(String p) {
int i = 1, j = 0;
next[1] = 0;
while (i < p.length()) {
if (j == 0 || p.charAt(i) == p.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
//计算nextval数组
public void get_nextval(String p) {
int i = 1, j = 0;
nextval[1] = 0;
while (i < p.length() - 1) {
if (j == 0 || p.charAt(i) == p.charAt(j)) {
i++;
j++;
if (p.charAt(i) != p.charAt(j))
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else {
j = nextval[j];
}
}
}
// KMP算法
public int kmp(String s, String p) {
//get_next(p);//计算next数组
get_nextval(p);
int i = 0, j = 1;//主串从第i个字符之后匹配
while (i < s.length() && j < p.length()) {
if (j == 0 || s.charAt(i) == p.charAt(j)) {//模式串首字符失配或相同继续匹配
i++;
j++;
} else {//失配
j = nextval[j];
}
}
if (j >= p.length())//找到
return i - p.length() - 1;
else
return 0;
}
}
public class test1 {

public static void main(String[] args) {
// TODO自动生成的方法存根
KMP test = new KMP();
String s = " acabaabaabcacaabc", t = " abaabcac";
System.out.println(test.kmp(s, t));
}
}

3 参考