KMP算法初探
KMP算法初探
[edit by xingoo]
kmp算法其实就是一种改进的字符串匹配算法。复杂度可以达到O(n+m)，n是参考字符串长度，m是匹配字符串长度。
传统的算法，就是匹配字符串与参考字符串挨个比较，如果相同就比较下一个，如果不相同，就返回上一次的结果，再重新比较。
如图1 如果失败则字符串会重新用S(参考字符串)的第二个，与T(匹配字符串)的第一个比较，知道全部符合查找，或找不到为止。
此时发现S[5] != T[5],因此用S[1]与T[0]进行比较。
此时发现S[1]!=T[0],因此用S[2]与T[0]比较。
此时，仍然不相等，继续后移。
此时，S[3] == T[0],继续比较，发现所有T元素都在S中找到，满足查找，返回开始匹配的下标3.
传统代码
1 int old_index(char * S,char * T){
2 int i=0;
3 int j=0;
4 while(i<strlen(S) && j<strlen(T)){
5 if( S[i] == T[j] ){
6 ++i;
7 ++j;
8 }
9 else{
10 i = i-j+1; //上一次的下一个
11 j=0;
12 }
13 }
14 if(j == strlen(T))
15 return i-strlen(T);
16 else
17 return -1;
18 }这种比较忽略了一个问题，就是在T中，abcabx，第一个字符串因为不跟第二个，第三个一样，因此，在一开始的匹配中，可以直接跳过比较，直接从S的第三个元素开始比较。这里就涉及到一个概念：最短子串对称匹配。
首先，初始化，当j=0时，next(j)=-1;
当j=1时，字符串0到j-1,只有"a",因此 next(j) = 0；
当j=2时，字符串0到j-1，字符串为"ab"，因此next(j) = 0；
当j=3时，字符串0到j-1，字符串为"abc",因此next(j) = 0;
当j=4时，字符串0到j-1，字符串为"abca",此时，前缀a在末尾出现，因此next(j) = 1;
当j=5时，字符串0到j-1，字符串为"abcab"，此时，前缀ab在末尾出现，因此next(j) = 2;
最后得到next的数组为"-1 0 0 0 1 2"。
按照这个方法：
ababab的next数组为"-1 0 0 1 2 3 4"
这里面，当j=5时，字符串"ababa",前缀是"aba",后缀也是"aba"，因此next值为3.
计算next数组详细代码
void getNext(char * T,int *next){
int i,j;
i=0;
j=-1;
next[0]=-1;
while(i<strlen(T)){
if(j == -1 || T[i] == T[j]){
++i;
++j;
next[i] = j;
}
else{
j = next[j];
}
}
}kmp匹配代码
int kmp(char* S,char * T){
int i=0;
int j=0;
int next[MAX];
getNext(T,next);
while(i<strlen(S) && j<strlen(T)){
printf("i %d-%c j %d-%c\n",i,S[i],j,T[j]);
if(j==0 || S[i]==T[j]){
++i;
++j;
}else{
j = next[j];
printf("j back to %d\n",j);
}
}
if(j == strlen(T))
return i-strlen(T);
else
return 0;
}全部代码
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #define MAX 20
5
6 void getNext(char * T,int *next);
7 int kmp(char * S,char * T);
8 int old_index(char * S,char * T);
9
10 int main()
11 {
12 char * s = "acabbabababc";
13 char * t = "ababab";
14
15 //printf("the pos is:%d\n\n",old_index(s,t));
16 //printf("the pos is:%d\n\n",old_index(m,t));
17 //printf("the pos is:%d\n\n",old_index(n,t));
18 printf("the pos is:%d\n",kmp(s,t));
19 return 0;
20 }
21
22 void getNext(char * T,int *next){
23 int i,j;
24 i=0;
25 j=-1;
26 next[0]=-1;
27 while(i<strlen(T)){
28 if(j == -1 || T[i] == T[j]){
29 ++i;
30 ++j;
31 next[i] = j;
32 }
33 else{
34 j = next[j];
35 }
36 }
37 }
38
39 int kmp(char* S,char * T){
40 int i=0;
41 int j=0;
42 int next[MAX];
43 getNext(T,next);
44 while(i<strlen(S) && j<strlen(T)){
45 printf("i %d-%c j %d-%c\n",i,S[i],j,T[j]);
46 if(j==0 || S[i]==T[j]){
47 ++i;
48 ++j;
49 }else{
50 j = next[j];
51 printf("j back to %d\n",j);
52 }
53 }
54 if(j == strlen(T))
55 return i-strlen(T);
56 else
57 return 0;
58 }
59 int old_index(char * S,char * T){
60 int i=0;
61 int j=0;
62 while(i<strlen(S) && j<strlen(T)){
63 if( S[i] == T[j] ){
64 ++i;
65 ++j;
66 }
67 else{
68 i = i-j+1; //上一次的下一个
69 j=0;
70 }
71 }
72 if(j == strlen(T))
73 return i-strlen(T);
74 else
75 return -1;
76 }运行结果
腾讯云开发者
