比特138

 找回密码
 立即注册
搜索
查看: 54|回复: 0

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

[复制链接]

485

主题

485

帖子

104

积分

初级会员

Rank: 2

金币
104
发表于 2020-4-25 17:07:37 | 显示全部楼层 |阅读模式
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 金币)
回复

使用道具 举报

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

本版积分规则

手机版|小黑屋|比特138 |网站地图

GMT+8, 2020-9-28 13:39 , Processed in 0.029585 second(s), 11 queries , Redis On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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