工控论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

查看: 2|回复: 0

数据结构KMP算法C语言源程序

[复制链接]

425

主题

431

帖子

296

积分

初级会员

Rank: 2

工控币
296
发表于 2020-4-25 17:08:09 | 显示全部楼层 |阅读模式
1.概述.
快速模式匹配算法,简称 KMP 算法,是在 BF 算法基础上改进得到的算法。 BF 算的实现过程就是 "傻瓜式" 地用模式串(假定为子串的串)与主串中的字符一一匹配,算法执行效率不高,所以为了减少算法的时间复杂度,特引出KMP算法
2.基本原理
example:
140712pzf9oshf47trhbo0.png

由此可以看出,每次匹配失败后模式串移动的距离不一定是 1,某些情况下一次移动多个位置,这就是 KMP 模式匹配算法
模式串移动距离的判断:
每次模式匹配失败后,计算模式串向后移动的距离是 KMP 算法中的核心部分。
其实,
匹配失败后模式串移动的距离和主串没有关系,只与模式串本身有关系。
给每个模式串配备一个数组(例如 next[]),用于存储模式串中每个字符对应指针 j 重定向的位置(也就是存储模式串的数组下标),比如 j=4,则该字符匹配失败后指针 j 指向模式串中第4 个字符
3.实现 next 数组的 C 语言代码:
142437vb6xnwb0q04bhjn1.png



4.next 数组的缺陷及改进
142653b09o45z27ex92pns.gif

当匹配失败时,Next 函数 开始继续进行模式匹配,但是从图中可以看到,这样做是没有必要的,纯属浪费时间

出现这种多余的操作,问题在当 T[i-1]==T[j-1] 成立时,没有继续对 i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判断。改进后的 Next 函数如下所示:
142754nttblob0fe3ou3ot.png
5.KMP的实现:附件 KMP算法C源码.rar  [预览压缩包] (1.18 KB, 售价: 1 工控币)
回复

使用道具 举报

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

本版积分规则

免责声明: 工控技术网(www.eleok.com)所有内容均为网友自行发布,不代表网站立场。如有版权纠纷,请联系本站删除:1370723259@qq.com

QQ|小黑屋|手机版|工控技术网 |网站地图

GMT+8, 2020-9-30 03:09

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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