QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

新鱼友

Rank: 1

积分
68
查看: 1717|回复: 10

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

[复制链接]
最佳答案
0 
累计签到:28 天
连续签到:0 天
p62273470 发表于 2011-12-3 15:13:32 171710 | 显示全部楼层 |阅读模式

马上注册加入鱼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 
累计签到:54 天
连续签到:0 天
嗜血灵异狂 发表于 2011-12-3 16:01:21 | 显示全部楼层
虽然我没学C  但是用汇编的思维去理解还是能看的懂一些  学习
最佳答案
0 
累计签到:446 天
连续签到:1 天
清/wx风 发表于 2011-12-3 16:19:54 | 显示全部楼层
学过了,理解有点难度,理解完就很好
最佳答案
0 
累计签到:28 天
连续签到:0 天
p62273470  楼主| 发表于 2011-12-3 16:57:57 | 显示全部楼层

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

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

发表回复

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

本版积分规则

关闭

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

    移动客户端下载(未启用)
    微信公众号

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

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.1 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2018-5-24 06:22

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