KMP模式匹配
2024-08-22 08:56:17
http://www.cnblogs.com/wangguchangqing/archive/2012/09/09/2677701.html
nextal[j+1]=next[j]+1
- KMP算法的实现
KMP算法的是对匹配的模式匹配算法的改进,在s[i]和p[j]匹配不成功时,不是对主串进行指针的回溯,而是在p[1,…,j-1]中,寻找一个p[k],
用s[i]和p[k]进行下一轮的匹配。其实现的最大问题就是如何的根据p[1,…,j-1]来求出p[k]。
在KMP算法的实现中,使用一个辅助数组next[],使用该数组保存p[j]匹配不成功时,要进行下一轮匹配的k的值.即是当s[i] 和 p[j]匹配不成功时,
用p[ next[j] ]来和s[i]进行下一轮匹配,k = next[j] .
对数组next[] 的求解,可以goolge到不少的方法,这里使用最简单的递推的方法:
首先假定next[0] = –1,那么当next[j] = k时,就有:p[0,…,j-1] == p[j-k+1,…,j-1]。
这时,若有p[k] = p[j] ,则p[0,….,k] = p[j-k+1,..,j-1,j],从而就有next[j+1] = next[j] + 1 = k +1 .
若p[k] != p[j] ,可以看着模式串对自身进行匹配的问题,即当匹配失败的时候,k值如何确定,k = next [k] .
求数组next[ ]的实现如下:
/* KMP进行模式匹配的辅助函数 模式串和主串匹配不成功时,下次和主串进行匹配的模式串的位置 */ void continue_prefix_function(const char * p , int * next) { int j ; int k ; next[0] = -1 ; j = 0 ; k = -1 ; while(j < strlen(p) - 1) { if( k == -1 || p[k] == p[j]) { j ++ ; k ++ ; next[j] = k ; }else { k =next[k] ; } } }
知道了当模式串和主串匹配不成功时,下一个和主串匹配的字符在模式串中的位置,在朴素的模式匹配的基础上很容易的写出KMP算法的代码如下:
/* 运用KMP算法的字符串模式匹配 在主串和模式串匹配不成功时,不对主串指针进行回溯, 例如用next[j],来指定下一次和主串进行匹配的模式串的位置 */ int match_kmp(const char * s ,const char * p,int pos) { int next[11] ; int i = pos ; int j = 0 ; continue_prefix_function(p,next) ; while(s[i] != '\0' && p[j] != '\0') { if(s[i] == p[j]) { i ++ ; j ++ ; }else { if(next[j] == -1) { i ++ ; j = 0 ; } else { j = next[j] ; } } } if(p[j] == '\0') return i - j ; else return -1 ; }
最新文章
- Python解析命令行读取参数 -- argparse模块
- 使用 PHPMailer 发送邮件
- window IIS6/IIS7取消脚本执行权限,禁止运行脚本木马
- [ActionScript 3.0] AS3.0 动态加载显示内容
- [Swift系列]001-入门准备
- IBM MQ Reason 2538(MQRC_HOST_NOT_AVAILABLE) 错误原因一例
- AVD设置屏幕大小
- 简单3D翻转
- (转)ASP.net中Timer无刷新定时器.
- 从源码看 angular/material2 中 dialog模块 的实现
- Activiti开发案例之activiti-app工作流导出图片
- NBIOT经典回答【转】
- springboot 报错 Content type &#39;application/x-www-form-urlencoded;charset=UTF-8&#39; not supported
- Python11 RabbitMQ Redis
- [福大软工] Z班 评测作业对应表
- SQL利用Case When Then多条件
- BZOJ 3143 游走(贪心+期望+高斯消元)
- linux及安全第八周总结——20135227黄晓妍
- iOS:CoreData数据库的使用四(数据库和UITableViewController以及NSFetchedResultsController一起使用)
- DRP经验总结
热门文章
- Opencv显示图片并监听鼠标坐标
- linux下的三种解压文件的命令?
- CustomerConfigHelper
- 锋利的jQuery-4--停止动画和判断是否处于动画状态(防止动画加入队列过多的办法)
- 锋利的jQuery-4--animate()的用法
- nginx 服务器重启命令,关闭 (转)
- [Effective JavaScript 笔记]第15条:当心局部块函数声明笨拙的作用域
- nginx: [error] invalid PID number ";"; in ";/usr/local/nginx/logs/nginx.pid";
- node.js模拟qq漂流瓶
- svn报错 400 Bad Request