下面这个小程序,可以演示 KMP 的匹配过程。
一直没有真正理解这个算法,昨天看了下算法导论。才懂了。
确实是一个相当精辟,相当巧妙的算法。太牛逼了!
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <string.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define MAX_LEN 256
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int tbl[MAX_LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char *str = "abbbbbbb";
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char *ptn = "bb";
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char spc[MAX_LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, j;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(spc, ' ', sizeof(spc));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tbl[0] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
for (i = 1; ptn[i]; i++)
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for (j = tbl[i - 1]; j && ptn[j] != ptn[i]; j = tbl[j]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if (ptn[j] == ptn[i])
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
j++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tbl[i] = j;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("table:\n");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for (i = 0; ptn[i]; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf(" %c", ptn[i]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("\n");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for (i = 0; ptn[i]; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%3d", tbl[i]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("\n");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
j = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
for (i = 0; str[i]; )
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("\nmatching #%d\n", i);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%s\n", str);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fwrite(spc, 1, i - j, stdout);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%s\n", ptn);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fwrite(spc, 1, i, stdout);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("^\n");
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
if (str[i] == ptn[j])
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
i++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
j++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("ok\n");
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
} else
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if (j)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
j = tbl[j - 1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
else
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
i++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("jumped to %d\n", j);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if (!ptn[j])
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("matched at %d\n", i);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
输出:
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