KMP算法的關(guān)鍵是根據(jù)給定的模式串W[1,m],定義一個next函數(shù)。next函數(shù)包含了模式串本身局部匹配的信息。
?? KMP算法的基本思想是：假設(shè)在模式匹配的進(jìn)程中，執(zhí)行T[i]和W[j]的匹配檢查。若T[i]=W[j]，則繼續(xù)檢查T[i+1]和W[j+1]是否匹配。若T[i]<>W[j]，則分成兩種情況：若j=1，則模式串右移一位，檢查T[i+1]和W[1]是否匹配；若1<j<=m，則模式串右移j-next(j)位，檢查T[i]和W[next(j)]是否匹配。重復(fù)此過程直到j(luò)=m或i=n結(jié)束。
/**************************************
?*
?*? KMP字符串匹配算法
?*
?*
?**************************************/
#include <stdio.h>
#include <string.h>
int next[10];
void getnext(char *p)
{
?int idx_p, len_p, k;
?
?idx_p = 0;
?len_p = strlen(p);
?k = -1;
?next[0] = -1;
?
?while(idx_p < len_p -1)
?{
? if ((k == -1) || *(p+idx_p) == *(p+k))
? {
?? idx_p = idx_p + 1;
?? k = k + 1;
?? next[idx_p] = k;
? }
? else
? {
?? k = next[k];
? }
?}
}
int kmp(char *s, char *p)
{
?int len_p, len_s, idx_p, idx_s;
?
?len_p = strlen(p);
?len_s = strlen(s);
?idx_p = idx_s = 0;
?
?while ((idx_p < len_p) && (idx_s < len_s))
?{
? /* 字符匹配或者要比較p中的第一個字符 */
? if ((idx_p == -1) || *(p+idx_p) == *(s+idx_s))
? {
?? idx_p = idx_p + 1; idx_s = idx_s +1;
? }
? else
? {
?? idx_p = next[idx_p];
? }
?}
?if (idx_p >= len_p)
?{
? return (idx_s - len_p);
?}
?else
?{
? return -1;
?}
}
int main()
{
?int pos, i;
?char s[50] = "abaaaabcabcacb";
?char p[10] = "aaaabca";
?
?getnext(p);
?if ((pos = kmp(s, p)) == -1)
?{
? fprintf(stderr, "String \"%s\" doesn't contain Pattern \"%s\"!\n", s, p);
?}
?else
?{
? printf("String \"%s\" contains Pattern \"%s\".\n The position of fisrt occur is %d\n", s, p, pos);
? printf("%s\n", s);
? for (i = 0; i < pos; i++)
?? printf(" ");
? printf("%s\n", p);
?}
?return 0;
}