KMP字符串模式匹配算法.doc

KMP算法是一种用于字符串匹配的算法,这个算法的高效之处在于当在某个位置匹配不成功的时候可以根据之前的匹配结果从模式字符串的另一个位置开始,而不必从头开始匹配字符串.
因此这个算法的关键在于,当某个位置的匹配不成功的时候,,其中next数组中的元素满足这个条件:next[j] = k,表示的是当模式字符串中的第j + 1个(这里是遵守标准C语言中数组元素从0开始的约定,以下不再说明)发生匹配不成功的情况时,应该从模式字符串的第k + ,那么KMP算法的实现如下:
// KMP字符串模式匹配算法
// 输入: S是主串,T是模式串,pos是S中的起始位置
// 输出: 如果匹配成功返回起始位置,否则返回-1
int KMP(PString S, PString T, int pos)
{
assert(NULL != S);
assert(NULL != T);
assert(pos >= 0);
assert(pos < S->length);

if (S->length < T->length)
return -1;
printf("主串\t = %s\n", S->str);
printf("模式串\t = %s\n", T->str);
int *next = (int *)malloc(T->length * sizeof(int));
// 得到模式串的next数组
GetNextArray(T, next);
int i, j;
for (i = pos, j = 0; i < S->length && j < T->length; )
{
// i是主串游标,j是模式串游标
if (-1 == j || // 模式串游标已经回退到第一个位置
S->str[i] == T->str[j]) // 当前字符匹配成功
{
// 满足以上两种情况时两个游标都要向前进一步
++i;
++j;
}
else // 匹配不成功,模式串游标回退到当前字符的next值
{
j = next[j];
}
}
free(next);
if (j >= T->length)
{
// 匹配成功
return i - T->length;
}
else
{
// 匹配不成功
return -1;
}
}
下面看看如何得到next数组.
这是一个递推求解的过程,初始的情况是next[0] = -1.
假设在某一个时刻有如下的等式成立:str[0...k-1] = str[j - k...j - 1],那么next[j] = k,在这个前提下,继续进行下一个字符的匹配.
1)如果str[0...k] = str[j - k...j],那么next[j + 1] = next[j] + 1 = k + 1.
2)反之,如果上面的匹配不成立,那么就要从next[k]开始进行新的匹配,如果成功的话,那么:
next[j + 1] = next[next[j]