说了这么多,我们可以来看看代码了。
/* 通过计算返回子串T的next数组。 */
void get_next(String T, int *next){
int i, j;
i = 1;
j = 0;
next[1] = 0;
/* 此处T[0]表示串T的长度 */
while (i < T[0]){
/* T[i]表示后缀的单个字符, */
/* T[j]表示前缀的单个字符 */
if (j == 0 || T[i] == T[j]){
++i;
++j;
next[i] = j;
}
else
/* 若字符不相同,则j值回溯 */
j = next[j];
}
}
这段代码的目的就是为了计算出当前要匹配的串T的next数组。
/* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
/* T非空,1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos){
/* i用于主串S当前位置下标值,若pos不为1,则从pos位置开始匹配 */
int i = pos;
/* j用于子串T中当前位置下标值 */
int j = 1;
/* 定义一next数组 */
int next[255];
/* 对串T作分析,得到next数组 */
get_next(T, next);
/* 若i小于S的长度且j小于T的长度时,循环继续 */
while (i <= S[0] && j <= T[0]){
/* 两字母相等则继续,相对于朴素算法增加了j=0判断 */
if (j == 0 || S[i] == T[j]){
++i;
++j;
}
/* 指针后退重新开始匹配 */
else{
/* j退回合适的位置,i值不变 */
j = next[j];
}
}
if (j > T[0])
return i - T[0];
else
return 0;
}
加粗的为相对于朴素匹配算法增加的代码,改动不算大,关键就是去掉了i值回溯的部分。对于get_next函数来说,若T的长度为m,因只涉及到简单的单循环,其时间复杂度为
O(m),而由于i值的不回溯,使得index_KMP算法效率得到了提高,while循环的时间复杂度为O(n)。因此,整个算法的时间复杂度为O(n+m)。相较于朴素模式匹配算法的 O((n-m+1)*m)来说,是要好一些。
这里也需要强调,KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势,否则两者差异并不明显。