糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

KMP 演示程序

下面这个小程序,可以演示 KMP 的匹配过程。
一直没有真正理解这个算法,昨天看了下算法导论。才懂了。
确实是一个相当精辟,相当巧妙的算法。太牛逼了!

#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

posted on 2010-04-29 12:48 糯米 阅读(411) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理