KMP

关于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
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define OK 1
#define ERROR 0
#define status int

typedef struct sstring
{
char ch[50];
int length;
}Sstring, *Lstring;

status InitString(Lstring& s);
status GetString(Lstring s, Lstring p);
status KMP(Lstring s, Lstring p, int pos, int* next);
status KNext(Lstring p, int* next);


int main()
{
Lstring s, p;
int* next;
InitString(s);
InitString(p);
GetString(s, p);
next = (int*)malloc(sizeof(int) * (p->length+1));
next[0] = 0;
KNext(p, next);
if (KMP(s, p, 1, next))
{
printf("存在");
}
else
{
printf("不存在");
}
return 0;
}

status InitString(Lstring& s)
{
s = (Lstring)malloc(sizeof(Sstring));
if (!s)
{
return ERROR;
}
s->length = 0;
return OK;
}

status GetString(Lstring s,Lstring p)
{
char c[100];
printf("请输入主串:");
scanf("%s", &s->ch[1]);
s->ch[0] = 'm';
s->length = strlen(s->ch)-1;
getchar();


printf("请输入子串:");
s->ch[0] = 'm';
scanf("%s", &p->ch[1]);
p->length = strlen(p->ch)-1;
getchar();
return OK;
}
status KMP(Lstring s, Lstring p, int pos, int* next)
{
int i, j;
i = pos;
j = 1;
while (i <= s->length && j <= p->length)
{
if (s->ch[i] == p->ch[j])
{
i++;
j++;
}
else if (j == 1)
{
i++;
}
else
{
j = next[j];
}
}
if (j > p->length)
{
return OK;
}
return ERROR;
}

status KNext(Lstring p, int* next)
{
int i, j;
i = 1;
j = 0;
next[1] = 0;
while (i <= p->length)
{
if (j == 0 || p->ch[i+1] == p->ch[j])
{
j++;
i++;
next[i] = j;
}
else
{
j = next[j];
}
}
return OK;
}

KMP算法的实现过程(被比对的是主串,比对的是字串)

从主串中查找是否含有子串

当比较 i 位置子串 和 主串中 k 位置的元素比较的时候

如果相同或者k = 0 的话 i++ k++ 继续比较下一个

如果不同的话,则让 k = next[k] 然后继续比较

直到 k 或者 i 超出子(主)串长度的时候停止比较

如果k超出范围的话 则比对成功

如果k没有超出范围的话,则比对失败

很多人不明白为什么 当比较不同的时候,KMP不用想BF算法那样 回到头从新开始比较,而是使用next数组回到对应的位置,下面我们来解释一下

其中最难实现的是 next 数组的获取:下面就我理解给大家讲一下

我们首先要懂得next数组的基本原理

next数组的基本原理就是:

当我们使用字串的第四个位置的元素和主串对应元素相比较的时候:

如果不相同的话,我们观察一下字串第四个位置和之前的元素有什么特点,明显的是 字串的一和二 和 字串的三和四相同,而且我们在子串和主串对应位置相比较的时候,当比较到字串的第四个位置的元素的时候,那么主串对应位置的前三个元素都和字串相同 ,所以我们不必返回 初始位置然后再从新比较, 我们只需要根据字串的特点来进行比较即刻,

由上面可知,在第四个位置和主串不相同的时候,那么 一二三位置的元素一定和主串位置元素相同,那么我们可以直接返回字串对应位置的next下标也就是2