下面這個(gè)小程序，可以演示 KMP 的匹配過程。
一直沒有真正理解這個(gè)算法，昨天看了下算法導(dǎo)論。才懂了。
確實(shí)是一個(gè)相當(dāng)精辟，相當(dāng)巧妙的算法。太牛逼了！
#include <stdio.h>
#include <string.h>
#define MAX_LEN 256
int tbl[MAX_LEN];
char *str = "abbbbbbb";
char *ptn = "bb";
char spc[MAX_LEN];
int main()
{
int i, j;
memset(spc, ' ', sizeof(spc));
tbl[0] = 0;
for (i = 1; ptn[i]; i++)
{
for (j = tbl[i - 1]; j && ptn[j] != ptn[i]; j = tbl[j]);
if (ptn[j] == ptn[i])
j++;
tbl[i] = j;
}
printf("table:\n");
for (i = 0; ptn[i]; i++)
printf(" %c", ptn[i]);
printf("\n");
for (i = 0; ptn[i]; i++)
printf("%3d", tbl[i]);
printf("\n");
j = 0;
for (i = 0; str[i]; )
{
printf("\nmatching #%d\n", i);
printf("%s\n", str);
fwrite(spc, 1, i - j, stdout);
printf("%s\n", ptn);
fwrite(spc, 1, i, stdout);
printf("^\n");
if (str[i] == ptn[j])
{
i++;
j++;
printf("ok\n");
} else
{
if (j)
j = tbl[j - 1];
else
i++;
printf("jumped to %d\n", j);
}
if (!ptn[j])
printf("matched at %d\n", i);
}
return 0;
}
輸出：
table:
b b
0 1
matching #0
abbbbbbb
bb
^
jumped to 0
matching #1
abbbbbbb
bb
^
ok
matching #2
abbbbbbb
bb
^
ok
matched at 3
matching #3
abbbbbbb
bb
^
jumped to 1
matching #3
abbbbbbb
bb
^
ok
matched at 4
matching #4
abbbbbbb
bb
^
jumped to 1
matching #4
abbbbbbb
bb
^
ok
matched at 5
matching #5
abbbbbbb
bb
^
jumped to 1
matching #5
abbbbbbb
bb
^
ok
matched at 6
matching #6
abbbbbbb
bb
^
jumped to 1
matching #6
abbbbbbb
bb
^
ok
matched at 7
matching #7
abbbbbbb
bb
^
jumped to 1
matching #7
abbbbbbb
bb
^
ok
matched at 8