字符串匹配算法-KMP

字符串匹配算法-KMP

说明

kmp的一些概述不做解释了, 请参考: kmp算法 (百度百科)
参考了 阮一峰的: 字符串匹配的KMP算法
使用 C 语言实现的算法

部分匹配表

指在一串字符串中, 前缀与后缀中所共有的字符

  • 前缀: 不包含字符串最后一个字符
  • 后缀: 不包含字符串第一个字符

例子:

字符串 (AHABAD)**
由此得出他们的部分匹配表为

A -> 0
前后都没有所有共有字符数所以为 0

AH -> 0
前缀: A
后缀: H
它们没有功能字符所有为 0

AHA -> 1
前缀: A, AH
后缀: A, HA
它们有共有的字符 共有数为 1

AHAB -> 0
前缀: A, AH, AHA
后缀: B, AB, HAB
它们没有共有字符所有为 0

AHABA -> 1
前缀: A, AH, AHA, AHAB
后缀: A, BA, ABA, HABA
它们有共有字符 共有数为 1

由此得出 AHABAD 的前缀表为

0 1 2 3 4 5
A H A B A D
-1 0 0 1 0 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
int* prefix(char* s){
/*
接收一个字符串,
返回一个部分匹配表
*/

int len = strlen(s),
i = 0,
j = -1,

*p = malloc(sizeof(int) * len);

p[0] = -1;

while(i < len - 1){
if(j == -1 || s[i] == s[j]){
p[++i] = ++j;
continue;
}
j = p[j];
}

return p;
}

变量 i && j && p 的作用
在这里 p 可以看作是一次回溯,
应为每当 if 条件不满足时 则进行一次回溯
那么此时 j 的位置就需要重置到 p[j]

部分匹配表生成过程 以字符串 AHABAD 为例

变量 A H A B A D
s = AHABAD \ A A H A \
j = -1 -1, 0 0,-1, 0 0, 1 1, 0, -1, 0 0, 1 \
i = 0 0, 1 1, 2 2, 3 3, 4 4, 5 \
p[0]=-1 p[1]=0 p[2]= 0 p[3]=1 p[4]=0 p[5]=1 \

kmp

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
//kmp匹配算法
int kmpSearch(char *t, char *s){
int t_len = strlen(t),
s_len = strlen(s);

int *p = prefix(s),
m = 0, //代表母串匹配到的位置
j = 0; // 代表字符匹配到的位置

while(t_len > m && s_len > j){
//j == -1 那么代表不和任何匹配直接向后移动以为
if(j == -1 || t[m] == s[j]){
m++;
j++;
continue;
}
//当不相等时, 就去查询部分匹配表
j = p[j];
}

if (j == s_len)
//返回匹配到的索引位置
return m - j;
return -1;
}

完整代码

所需头文件:

string.h stdlib.h

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
//部分匹配表算法
int* prefix(char* s){
//prefix table
int len = strlen(s),
i = 0,
j = -1,
*p = malloc(sizeof(int) * len);
p[0] = -1;

while(i < len - 1){
if(j == -1 || s[i] == s[j]){
p[++i] = ++j;
continue;
}
j = p[j];
}

return p;
}

//kmp
int kmpSearch(char *t, char *s){
int t_len = strlen(t),
s_len = strlen(s);

int *p = prefix(s),
m = 0,
j = 0;

while(t_len > m && s_len > j){
if(j == -1 || t[m] == s[j]){
m++;
j++;
continue;
}
j = p[j];
}

if (j == s_len)
return m - j;
return -1;

}