模式匹配(kmp)代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】模式匹配(kmp)

作者:壮壮 / 发布于2016/4/21/ 355

//模式匹配,kmp算法,复杂度O(m+n)
//返回匹配位置,-1表示匹配失败,传入匹配串和模式串和长度
//可更改元素类型,更换匹配函数
#define MAXN 10000
#define _match(a,b) ((a)==(b))
typedef char elem_t;

int pat_match(int ls,elem_t* str,int lp,elem_t* pat){
	int fail[MAXN]={-1},i=0,j;
	for (j=1;j<lp;j++){
		for (i=fail[j-1];i>=0&&!_match(pat[i+1],pat[j]);i=fail[i]);
		fail[j]=(_match(pat[i+1],pat[j])?i+1:-1);
	}
	for (i=j=0;i<ls&&j<lp;i++)
		if (_match(str[i],pat[j]))
			j++;
		else if (j)
			j=fail[j-1]+1,i--;
	return j==lp?(i-lp):-1;
}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　模式匹配(kmp)　

同语言下

.C分鱼问题
.链表
.最大连续和
.编码字符串
.libiconv字符编码处理及判断字符串是否为utf8
.一组数中两两二元组，差最大有几对，差最小呢？（数组
.通过管道获取一个进程的执行状态
.多关键字排序
.字符串字典序排序
.3元一次方程(牛顿迭代法求方程的根)

可能有用的

.SQL查询多列合并成一行用逗号隔开
.一行一行读取txt的内容
.C#动态修改文件夹名称(FSO实现，不移动文件)
.c# 移动文件或文件夹
.c#图片添加水印
.Java PDF转换成图片并输出给前台展示
.网站后台修改图片尺寸代码
.处理大图片在缩略图时的展示
.实现对图片上传的接收
.判断用户输入的是否为IP地址

壮壮贡献的其它代码(8)

.mybatis如何遍历Map的key和value
.udf使用间隔
.获取 HTTP 服务器的信息
.提取 HTML 文档中的链接和图片
.网络相关
.音频采集
.字符串字串判断
.模式匹配(kmp)