数据结构与算法11-字符串匹配KMP
2020-04-27 本文已影响0人
随意昵称你能懂得
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。
KMP算法的时间复杂度O(m+n)。
代码中的T[0]和S[0]为数组长度。
/*
KMP 算法
*/
void get_next(String T, int *next) {
int i, j;
i = 0;
j = 1;
next[1] = 0;
while (j < T[0]) {
if (i == 0 || T[i] == T[j]) {
i++;
j++;
next[j] = i;
} else {
i = next[i];
}
}
}
int Index_KMP(String S, String T, int pos) {
int next[MAXSIZE];
get_next(T, next);
int i = pos;
int j = 1;
while (i < S[0] && j <= T[0]) {
if (j == 0 || S[i] == T[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j > T[0]) {
return i - T[0];
} else {
return -1;
}
}
代码优化,减少回退的长度
/*
KMP优化
*/
void get_next(String T, int *next) {
int i, j;
i = 0;
j = 1;
next[1] = 0;
while (j < T[0]) {
if (i == 0 || T[i] == T[j]) {
i++;
j++;
if (T[i] != T[j]) {
next[j] = i;
} else {
next[j] = next[i];
}
} else {
i = next[i];
}
}