ITPub博客

首页 > Linux操作系统 > Linux操作系统 > KMP字符串模式匹配

KMP字符串模式匹配

原创 Linux操作系统 作者:壹頁書 时间:2015-09-04 19:53:21 0 删除 编辑
参考:
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

http://blog.csdn.net/v_july_v/article/details/7041827


  1. #include <stdio.h>
  2. #include <string.h>

  3. void GetNext(char* p,int next[])
  4. {
  5.     int pLen = strlen(p);
  6.     next[0] = -1;
  7.     int k = -1;
  8.     int j = 0;
  9.     while (j < pLen - 1)
  10.     {
  11.         printf("j=%i\tk=%i\t",j,k);
  12.         printf("%c\t",p[j]);
  13.         printf("%c\n",p[k]);

  14.         if (k == -1 || p[j] == p[k])
  15.         {
  16.             ++k;
  17.             ++j;
  18.             next[j] = k;
  19.         }
  20.         else
  21.         {
  22.             k = next[k];
  23.         }
  24.     }


  25.     printf("---------------------\n");
  26.     int i;
  27.     for (i=0;i<pLen;i++){
  28.         printf("next[%i]:%i\n",i,next[i]);
  29.     }
  30. }
  31. int KmpSearch(char* s, char* p)
  32. {
  33.     int i = 0;
  34.     int j = 0;
  35.     int sLen = strlen(s);
  36.     int pLen = strlen(p);
  37.     int next[pLen];
  38.     GetNext(p,next);
  39.     while (i < sLen && j < pLen)
  40.     {
  41.         if (j == -1 || s[i] == p[j])
  42.         {
  43.             i++;
  44.             j++;
  45.         }
  46.         else
  47.         {
  48.             j = next[j];
  49.         }
  50.     }
  51.     if (j == pLen)
  52.         return i - j;
  53.     else
  54.         return -1;
  55. }


  56. void main(){
  57.     char* s="acabaabaabcacaabc";
  58.     char* p="abaabc";
  59.     int i=KmpSearch(s,p);
  60.     printf("=====================\n");
  61.     printf("%s\n",s);
  62.     printf("%s\n",p);
  63.     printf("%i\n",i);
  64. }

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29254281/viewspace-1791038/,如需转载,请注明出处,否则将追究法律责任。

下一篇: 两种丢失更新
请登录后发表评论 登录
全部评论

注册时间:2013-10-19

  • 博文量
    621
  • 访问量
    5992757