鱼C论坛

 找回密码
 立即注册
查看: 1854|回复: 10

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

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

马上注册加入鱼C,享用更多服务吧^_^

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

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, 下载次数: 23)

评分

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

查看全部评分

最佳答案
0 
发表于 2011-12-3 16:01:21 | 显示全部楼层
虽然我没学C  但是用汇编的思维去理解还是能看的懂一些  学习
最佳答案
0 
发表于 2011-12-3 16:19:54 | 显示全部楼层
学过了,理解有点难度,理解完就很好
最佳答案
0 
 楼主| 发表于 2011-12-3 16:57:57 | 显示全部楼层

后面写的很乱,你应该只看得懂前面的吧!没办法,有时候很难用人类语言去描述这些东西,虽然逻辑思维上并不是特别难!
最佳答案
0 
 楼主| 发表于 2011-12-3 17:03:48 | 显示全部楼层
清/wx风 发表于 2011-12-3 16:19
学过了,理解有点难度,理解完就很好

确实,起初看的让人蛋疼!
最佳答案
0 
发表于 2012-3-26 21:05:56 | 显示全部楼层
我盯住KMP算法两天才搞清楚思路, 实现倒是不难!
KMP 算法还有一个缺陷: 只盯住模式串!
比如: asbsnkkkkkkkkkkkkkkkkkkkkkkkkkkkkk;
         absslalal;
KMP 无法使时间复杂度达到最优!
最佳答案
0 
发表于 2012-3-28 17:48:42 | 显示全部楼层
KMP 我搞晕了  感觉还没能真正理解是不是  数学基础不好啊
最佳答案
0 
发表于 2012-3-28 18:14:41 | 显示全部楼层
next数组是怎么得出来的啊 云里雾里的
最佳答案
0 
发表于 2012-3-29 12:59:23 | 显示全部楼层
你好,顶贴赚币
最佳答案
11 
发表于 2018-4-26 08:42:03 | 显示全部楼层
好帖,顶起,这个KMP估计是串操作里的核心了
最佳答案
0 
发表于 2018-5-15 21:26:37 | 显示全部楼层
为什么我把你的代码用C++的编译器运行有错误啊?

*滑块验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号 )

GMT+8, 2018-7-19 23:09

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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