补充：KMP模式匹配算法_kmp如何根据next数组匹配

6.2 KMP模式匹配算法

如果你没有看过6.1的话，我建议回头看看，因为这是基于6.1的补充，下面是链接：
串的实现详解和朴素的模式匹配算法

6.2.1 KMP模式匹配算法原理

KMP模式匹配算法是优于朴素匹配算法的，假设有主串S="abcdefgh"，子串T="abcdx"，如果使用朴素匹配算法，会是下面这种情况：

第一次匹配的时候，在第五个位置已经匹配失败，但是朴素匹配算法还要将i回溯，其实没有必要，第一次匹配失败后可以直接使i=6，即不修改i的值，只需要修改j值，如下图：

我们再来看下面一种情况，主串是S="abcababc"，子串是T="abcab"

在左图，子串中第四位的a和第五位的b已经和主串相应位置在第一次比较过了，所以子串中的第一位的a，第二位的b，和主串中第四位，第五位肯定相同，没有必要比较，所以j不需要回溯成1，只需要回溯成3就可以。

所以j回溯和主串无关，只和子串前后缀相似度有关。因此，我们需要一个next数组，来表示子串的相似度，可以来确定回溯到哪里。

6.2.2 next数组的推导

子串 T="abcdx"，推导图如下：

在图①，next[1]默认等于0，当T[k]==T[i]的时候，i和k都加1，将k赋值给next[i]。当T[k]!=T[i]的时候，k值回溯，将next[k]的值赋值给k。


代码如下：

/*获取next数组*/
void get_next(String T,int *next){
    int i,k;
    i=1;
    k=0;
    next[1]=0;
    while(i<T[0]){
        if(k==0 || T[i]==T[k]){
            ++i;
            ++k;
            next[i]=k;
        }else{
            k=next[k];      //k回溯
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.2.3 利用next数组匹配

利用next数组匹配，与朴素模式匹配算法相比，除了i值不需要回溯，还要j通过next数组回溯，而不是直接j=1，代码如下：

/*返回子串T在主串S中第pos个字符之后的位置*/
int Index_KMP(String S,String T,int pos){
    int i = pos;        //S的下标
    int j = 1;          //T的下标
    int next[255];
    get_next(T,next);
    while(i<=S[0] && j<=T[0]){
        if(j==0 || S[i]==T[j]){
            ++i;
            ++j;
        }else{
            j = next[j];       //j退回合适位置，i不变
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

6.2.4 KMP模式匹配优化-----优化next数组

假设有子串T="aaaaab"，主串S="aaacdefgh"。子串T的next数组为0 1 2 3 4 5，当第一次匹配失败的时候(i=4，j=4)，j回溯，j=next[j]=next[4]=3，其实j=3处，还是字母a，先前比较过一次，没有必要再进行比较，j应该回溯成0。所以引入一个nextval数组，来完成这种回溯。

代码如下：

/*改良版nextval数组*/
void get_nextval(String T,int *nextval){
    int i,k;
    i=1;
    k=0;
    nextval[1]=0;
    while(i<T[0]){
        if(k==0 || T[i]==T[k]){
            ++i;
            ++k;
            if(T[i]!=T[k])
                nextval[i]=k;
            else
                nextval[i]=nextval[k];      //若和前缀字符相同，则将前缀字符的nextval赋值给在i位置的nextval
        }else{
            k=nextval[k];      //k回溯
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

和原本的next数组相比，多了一条判断语句。

6.2.4 测试代码

这边附上完整代码，供给大家测试：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<windows.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100

typedef int Status;
typedef int ElemType;

typedef char String[MAXSIZE+1];     //0号单元存放串的长度

/*生成一个值为chars的串T*/
Status StrAssign(String T,char *chars){
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else{
        T[0] = strlen(chars);
        for(i=1;i<=T[0];i++){
            T[i] = *(chars+i-1);
        }
        return OK;
    }
}

/*清楚串*/
Status ClearString(String S){
    S[0] = 0;
    return OK;
}

/*输出串*/
void StrPrint(String T){
    for(int i=1;i<=T[0];i++){
        printf("%c",T[i]);
    }
    printf("\n");
}

/*  输出Next数组值。 */
void NextPrint(int next[],int length){
    int i;
    for(i=1;i<=length;i++)
        printf("%d",next[i]);

    printf("\n");
}

/* 返回串的元素个数 */
int StrLength(String S){ 
	return S[0];
}

/*获取next数组*/
void get_next(String T,int *next){
    int i,k;
    i=1;
    k=0;
    next[1]=0;
    while(i<T[0]){
        if(k==0 || T[i]==T[k]){
            ++i;
            ++k;
            next[i]=k;
        }else{
            k=next[k];      //k回溯
        }
    }
}

/*改良版nextval数组*/
void get_nextval(String T,int *nextval){
    int i,k;
    i=1;
    k=0;
    nextval[1]=0;
    while(i<T[0]){
        if(k==0 || T[i]==T[k]){
            ++i;
            ++k;
            if(T[i]!=T[k])
                nextval[i]=k;
            else
                nextval[i]=nextval[k];      //若和前缀字符相同，则将前缀字符的nextval赋值给在i位置的nextval
        }else{
            k=nextval[k];      //k回溯
        }
    }
}


/*返回子串T在主串S中第pos个字符之后的位置*/
int Index_KMP(String S,String T,int pos){
    int i = pos;        //S的下标
    int j = 1;          //T的下标
    int next[255];
    get_next(T,next);
    while(i<=S[0] && j<=T[0]){
        if(j==0 || S[i]==T[j]){
            ++i;
            ++j;
        }else{
            j = next[j];       //j退回合适位置，i不变
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return 0;
    }
}


/*改良版KMP匹配*/
int Index_KMP1(String S,String T,int pos){
    int i = pos;        //S的下标
    int j = 1;          //T的下标
    int next[255];
    get_nextval(T,next);
    while(i<=S[0] && j<=T[0]){
        if(j==0 || S[i]==T[j]){
            ++i;
            ++j;
        }else{
            j = next[j];       //j退回合适位置，i不变
        }
    }
    if(j>T[0]){
        return i-T[0];
    }else{
        return 0;
    }
}

/* 朴素的模式匹配法 */
int Index(String S, String T, int pos) 
{
	int i = pos;	/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
	int j = 1;				/* j用于子串T中当前位置下标值 */
	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
	{
		if (S[i] == T[j]) 	/* 两字母相等则继续 */
      	{
			++i;
         	++j; 
      	} 
      	else 				/* 指针后退重新开始匹配 */
      	{  
         	i = i-j+2;		/* i退回到上次匹配首位的下一位 */
         	j = 1; 			/* j退回到子串T的首位 */
      	}      
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}


int main(){
	int i,*p;
	String s1,s2;

	
	StrAssign(s1,"abcdex");
	printf("子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("Next为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"abcabx");
	printf("子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("Next为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"ababaaaba");
	printf("子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("Next为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"aaaaaaaab");
	printf("子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("Next为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"ababaaaba");
	printf("   子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("   Next为: ");
	NextPrint(p,StrLength(s1));
	get_nextval(s1,p); 
	printf("NextVal为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"aaaaaaaab");
	printf("   子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("   Next为: ");
	NextPrint(p,StrLength(s1));
	get_nextval(s1,p); 
	printf("NextVal为: ");
	NextPrint(p,StrLength(s1));

	printf("\n");

	StrAssign(s1,"00000000000000000000000000000000000000000000000001");
	printf("主串为: ");
	StrPrint(s1);
	StrAssign(s2,"0000000001");
	printf("子串为: ");
	StrPrint(s2);
	printf("\n");

	printf("主串和子串在第%d个字符处首次匹配（朴素模式匹配算法）\n",Index(s1,s2,1));

	printf("主串和子串在第%d个字符处首次匹配（KMP算法） \n",Index_KMP(s1,s2,1));
	printf("主串和子串在第%d个字符处首次匹配（KMP改良算法） \n",Index_KMP1(s1,s2,1));

    system("pause");
	return 0;
}
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254

运行结果：

子串为: abcdex
Next为: 011111

子串为: abcabx
Next为: 011123

子串为: ababaaaba
Next为: 011234223

子串为: aaaaaaaab
Next为: 012345678

   子串为: ababaaaba
   Next为: 011234223
NextVal为: 010104210

   子串为: aaaaaaaab
   Next为: 012345678
NextVal为: 000000008

主串为: 00000000000000000000000000000000000000000000000001
子串为: 0000000001

主串和子串在第41个字符处首次匹配（朴素模式匹配算法）
主串和子串在第41个字符处首次匹配（KMP算法）
主串和子串在第41个字符处首次匹配（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