鱼C论坛

 找回密码
 立即注册
查看: 4896|回复: 11

[争议讨论] 我对kmp算法的理解

[复制链接]
发表于 2011-12-3 15:13:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 p62273470 于 2011-12-3 15:13 编辑

■概念:
什么是kmp算法
kmp算法是一种改进的字符串匹配算法。

什么是字符串匹配
字符串匹配就是在一个大的字符串S中搜索某个字符串T的出现位置。其中,S称为文本串,T称为模式串;

字符串匹配算法有什么用
例如:在Word等编辑器中有这样一个功能,在“查找”对话框中输入待查找的内容(常见的是查找某个字或词),系
统会在整个文档中进行查找,将与待查找内容相匹配的部分高亮显示。

■先看看一般匹配算法
例子:主串S为ababcabcacbab,模式串T为abcac;

一般的匹配算法为:
i = 0;
j = 0;
while(j<模式串的长度)
{
     if(S == T[j])
    {
        ++i;
        ++j

    }
    else
    {
        i++;
        j = 0;
    }

    if(i>主串T的长度)
    {
        输出“字符串无法匹配!“;
        退出循环;
    }
}

//程序运行结束,i为匹配的终止位置!

①当模式串T中任何字符与主串S中的字符不相等时,整个模式串都前进一位,重新从模式串第一个字符a开始比较
匹配过程如下图:
1,ababcabcacbab
      abcac
      相等
2,ababcabcacbab
      abcac
     相等
3,ababcabcacbab
      abcac
     不相等,根据①,有步骤4,
4,ababcabcacbab
        abcac
     不相等,根据①,有步骤5
5,ababcabcacbab
          abcac
       相等
6,此处省略比较3次,因为这4次都相等
9,ababcabcacbab
            abcac
     不相等,根据①,有步骤10
10,ababcabcacbab
              abcac
       不相等,根据①,有步骤11
11,ababcabcacbab
                 abcac
     不相等,根据①,有步骤12
12,ababcabcacbab
                   abcac
     相等,继续比较4次就可以得出结果了

一共需比较16次才能比较出结果

flash演示匹配过程 字符串匹配一般过程.rar (3.88 KB, 下载次数: 25)


分析:这种算法虽然简单,但效率太低!




■下面看看kmp算法!
kmp的思路其实不难,难的是怎样用语言来描述它!我们先看下面的内容;

我们定义一个数组next,next的大小比模式串的长度大1,当模式串为abcac时,那么next数组的大小为6,我们让next[0] = 0,因为我们用不到next[0],放一边!接下来我们做下面的比较。
比较规则如下:
去掉模式串T中的第一个字符,则变为bcac,则bb后面的所有字符为bcc后面所有的字符为bcaa后面所有的字符为bcacc后面所有的字符为bcac,把b,bc,bca,bcac依次和模式串abcac比较,比较的顺序是从右到左,
当符合以下条件时记录下信息:
1,当最右边的字符和模式串中的处于对齐位置的字符不相同,且其他字符和模式串中处于对齐位置上的字符相等时。
2,当最右边的字符和模式串中处于对齐位置的字符相同,且其他字符和模式串中处于对齐位置上的字符相等时。
3,取其中长度最长的!
流程如下:
模式串中的第一个字符的next值固定为0,所以next[1] = 0;

1,比较b      
        b
        abcac
   不相等,且比较完毕,符合比较规则,记录下信息为:b为模式串中的第2(i=2)个字符,比较到第1(j=1)个字符a就完毕,则next= j(next[2] = 1);

2,比较bc
        
     2.1    bc
                 abcac
             不相等,符合比较规则,记录下信息为:c为模式串中的第3(i=3)个字符,比较到第1(j=1)个字符a
     2.2    bc
              abcac
            不相等,但不符合比较规则,且比较完毕,取上面的信息:则next = j(next[3] = 1);

3,比较bca
    3.1   bca
                abcac
            相等,符合规则,记录信息:a为模式串中的第4(i=4)个字符,比较到第1(j=1)个字符,next[4] = next[1];
    3.2  bca
              abcac
           不相等,不符合规则,不记录信息,继续;
     3.3 bca
           abcac
           不相等,不符合规则,不记录信息,取上面的信息next = next[j](next[4] = next[1]=0);

4,比较bcac
     
     4.1  bcac
                  abcac
        不相等,符合规则,记录信息:c为模式串中的第5(i=5)个字符,比较到第1(j=1)个字符a
     4.2 bcac
               abcac
        不相等,符合规则,记录信息:c为模式串中的第5(i=5)个字符,比较到第2(j=2)个字符b
    4.3
    4.4   此处省略,因为都不符合规则,则取4.2的,因为比较长度为2,大于4.1的,信息应为:next = j(next[5 ]= 2);
所以next数组为:01102,next数组的意思是:当模式串中第j个字符和主串中第i个字符比较不等时,直接换模式串中第next[j]和主串中的那个第i个字符比较。于是有下面的
①当模式串T中的第1个字符a与主串S中的字符不相等时,把模式串T的第一个字符a和主串S的下一个字符比较
②当模式串T中的第2个字符b与主串S中的字符不相等时,把模式串T的第一个字符a和主串S的当前字符比较
③当模式串T中的第3个字符c与主串S中的字符不相等时,把模式串T的第一个字符a和主串S的当前字符比较
④当模式串T中的第4个字符a与主串S中的字符不相等时,把模式串T的第一个字符a和主串S的下一个字符比较
⑤当模式串T中的第5个字符c与主串S中的字符不相等时,把模式串T的第二个字符b和主串S的当前字符比较

匹配流程如下:
1,ababcabcacbab
      abcac

          相等
2,ababcabcacbab
      abcac
          相等
3,ababcabcacbab
      abcac
         不相等,根据③,要把模式串T中的第一个字符a和主串S中的b比较,于是有下面的步骤4
4,ababcabcacbab
            abcac
        不相等,根据①,要把模式串T中的第一个字符a和主串S中的c比较,于是有步骤5;
5,ababcabcacbab
              abcac
       不相等,根据①,要把模式串T中的第一个字符a和主串S中的c比较,于是有下面的步骤6;
6,ababcabcacbab
                abcac
       相等,继续比较下去都相等了。
再比较4次就能得出正确结果了,所以一共只需比较10次,就算得出结果;


kmp关键在于理解得出next数组的道理!

■下面是kmp算法的代码:

  1. #include <iostream>
  2. #include <string.h>
  3. using namespace std;
  4. int Get_Next(char *p,int *next); //得到next数组
  5. int pipei(char *s,char *t,int *next); //匹配函数
  6. int Get_Next(char *p,int *next)
  7. /*
  8. 指针表示模式串的数组的头指针,指针next表示next数组的头指针
  9. */
  10. {

  11. int i=1;next[1] = 0;
  12. int j = 0;
  13. int len = strlen(p);
  14. while (i < len)
  15. {
  16. if (j == 0 || p[i] == p[j])
  17. {
  18. ++j;
  19. ++i;
  20. if(p[i] != p[j])next[i] = j;
  21. else
  22. {
  23. next[i] = next[j];
  24. }
  25. }
  26. else j = next[j];

  27. }

  28. for (int h=1;h<len;h++)
  29. {
  30. cout<<next[h];
  31. }

  32. return 0;
  33. }

  34. int pipei(char *s,char *t,int *next)
  35. /*
  36. s表示主串的头指针,t表示模式串的头指针,next表示next数组的头指针
  37. */
  38. {
  39. int i=0,j=1;
  40. int ilen = strlen(s);
  41. int jlen = strlen(t);
  42. while (j<jlen&&i<ilen)
  43. {
  44. if(s[i] == t[j])
  45. {
  46. i++;
  47. j++;
  48. }
  49. else
  50. {
  51. if (next[j] == 0)
  52. {
  53. i++;
  54. j = 1;
  55. }
  56. else
  57. {
  58. j = next[j]-1;
  59. }

  60. }
  61. }
  62. cout<<i<<" "<<jlen<<endl;
  63. return i+1-jlen+1;
  64. }

  65. void main()
  66. {

  67. int len = 0;
  68. printf("请输入模式串的个数:");
  69. cin>>len;
  70. int *n = new int[len+1];
  71. char *t = new char[len + 2];
  72. char s[100];
  73. memset(n,0,len+1);
  74. memset(t,0,len+2);
  75. memset(s,0,100);
  76. cout<<"输入模式串:";
  77. for (int h=1; h<=len; h++)
  78. {
  79. cin>>t[h];
  80. }
  81. t[0] = 'g';
  82. Get_Next(t,n);
  83. cout<<"next数组为:";
  84. for (h=1;h<=len;h++)
  85. {
  86. cout<<n[h];
  87. }

  88. cout<<"输入主串:";
  89. cin>>s;

  90. int start_str = pipei(s,t,n);
  91. cout<<endl;
  92. cout<<"匹配的起始位置为:"<<start_str;


  93. }
复制代码






评分

参与人数 1荣誉 +8 鱼币 +10 收起 理由
故乡的风 + 8 + 10 很久没来这里,今天偶然看到,很不错.赞一个!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-3 16:01:21 | 显示全部楼层
虽然我没学C  但是用汇编的思维去理解还是能看的懂一些  学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-3 16:19:54 | 显示全部楼层
学过了,理解有点难度,理解完就很好
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-12-3 16:57:57 | 显示全部楼层

后面写的很乱,你应该只看得懂前面的吧!没办法,有时候很难用人类语言去描述这些东西,虽然逻辑思维上并不是特别难!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-12-3 17:03:48 | 显示全部楼层
清/wx风 发表于 2011-12-3 16:19
学过了,理解有点难度,理解完就很好

确实,起初看的让人蛋疼!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-3-26 21:05:56 | 显示全部楼层
我盯住KMP算法两天才搞清楚思路, 实现倒是不难!
KMP 算法还有一个缺陷: 只盯住模式串!
比如: asbsnkkkkkkkkkkkkkkkkkkkkkkkkkkkkk;
         absslalal;
KMP 无法使时间复杂度达到最优!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-3-28 17:48:42 | 显示全部楼层
KMP 我搞晕了  感觉还没能真正理解是不是  数学基础不好啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-3-28 18:14:41 | 显示全部楼层
next数组是怎么得出来的啊 云里雾里的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-3-29 12:59:23 | 显示全部楼层
你好,顶贴赚币
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2018-4-26 08:42:03 | 显示全部楼层
好帖,顶起,这个KMP估计是串操作里的核心了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-15 21:26:37 | 显示全部楼层
为什么我把你的代码用C++的编译器运行有错误啊?

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-8-11 22:13:57 | 显示全部楼层
不太懂这种类型写的语言(个别代码不懂)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 23:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表