更新时间:2015-10-15 23:02:02浏览次数:1+次
大致的代码如下:
static void cal_next_table(const char *pattern, int len, int *table)
{
int i,j;
/* table[0] 为哨兵 */
table[0] = 1;
for (i = 1; i <= len; ++i) {
table[i] = table[i-1];
for (j = table[i]; j < i; ++j) {
if (0 != strncmp(pattern, pattern+j, i-j-1)) {
table[i]++;
}
else {
break;
}
}
}
}
通过上面的函数,将生成右移的table表。当第n个不匹配时,可以向右滑动table[n]个字符。
下面是测试代码:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
static void cal_next_table(const char *pattern, int len, int *table)
{
int i,j;
table[0] = 1;
for (i = 1; i <= len; ++i) {
table[i] = table[i-1];
for (j = table[i]; j < i; ++j) {
if (0 != strncmp(pattern, pattern+j, i-j-1)) {
table[i]++;
}
else {
break;
}
}
}
}
int main()
{
char pattern[] = "abcabcdef";
int table[sizeof(pattern)+1] = {};
cal_next_table(pattern, sizeof(pattern), table);
int i;
printf("%s\n", pattern);
for (i = 1; i < sizeof(pattern); ++i) {
printf("%d", table[i]);
}
printf("\n");
return 0;
}
结果如下:
abcabcdef
112333378
最后总结一下,我们从KMP算法中可以获得什么?除了知道这个字符串匹配算法,我们还要争取 获得更多的东西,比如即尽可能的从已经处理过得操作或数据中获得更多的信息。
相关资讯