KMP算法的关键是根据给定的模式串W[1,m],定义一个next函数。next函数包含了模式串本身局部匹配的信息。
KMP算法的基本思想是：假设在模式匹配的进程中，执行T[i]和W[j]的匹配检查。若T[i]=W[j]，则继续检查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)]是否匹配。重复此过程直到j=m或i=n结束。
/**************************************
*
* 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;
}