首页 > 编程语言 >串的模式匹配算法

串的模式匹配算法

时间:2022-09-18 21:46:46浏览次数:74  
标签:字符 return int next char 算法 匹配 模式匹配

一、算法设计思想

1.简单模式匹配算法

从主串的第一个位置开始和模式串的第一个字符开始比较,相等继续比较下一个字符;否则从主串的下一个字符和模式串的第一个字符重新开始比较,以此类推,直到比较完模式串的所有字符。匹配成功返回模式串在主串中的位置,否则返回0。

2.KMP

二、代码实现

1.

int Index(char str[],char substr[])
{
	int i=1,j=1,k=i; //从1开始存储,k表示主串匹配开始位置,匹配失败自增1
	while(i<=str[0]&&j<=substr[0]){
		if(str[i]==substr[j]){
			++i;
			++j;
		}
		else{
			j=1;
			i=++k;
		}
	}
	if(j>substr[0]) 
		return k;
	else 
		return 0;
}

2.KMP

//计算next数组(模式串的自我匹配)
void get_next(char T[],int next[])
{
	int i=1,j=0; //串从下标1开始存储,0位置存储串长度
	next[1]=0;
	while(i<T[0]){
		if(j==0||T[i]==T[j]){
			++i;
			++j;
			next[i]=j;
		}
		else
			j=next[j];
	}
}

//kmp匹配算法
int KMP(char S[],char T[],int next[])
{
	int i=1,j=1;
	while(i<=S[0]&&j<=T[0]){
		if(j==0||S[i]==T[j]){
			++i;
			++j;
		}
		else
			j=next[j];
	}
	if(j>T[0])
		return i-T[0]; //匹配位置
	else 
		return 0;
}

三、时间复杂度分析

标签:字符,return,int,next,char,算法,匹配,模式匹配
From: https://www.cnblogs.com/unravel-CAT/p/16667599.html

相关文章

  • k最近邻算法
    #K最近邻算法##概述K最近邻算法适用于找出距离A坐标最近的几个点,可以用来做推荐系统##计算公式以及模拟K最近邻算法有两个公式:距离公式,相似度公式(余弦)###距离公式......
  • 平滑的加权轮询均衡算法
    前言在反向代理、路由、分布式应用调度等场景中通常都需要用到负载均衡算法,负载均衡的关键要点是“均衡”,即确保调用请求能均衡的落到多个处理节点上,负载均衡算法一般使用......
  • 算法性能分析
    算法的性能分析概括成时间复杂度和空间复杂度两部分;1.时间复杂度通常指算法运行的时间(大O记法只保留最高次项,忽略低次项和常数项)2.空间复杂度......
  • KMP算法的底层理解
    KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。KMP的精髓所在就是前缀表。(下面用next[]数组来表......
  • 通关基本算法 day_03 -- 二分算法
    整数二分本质如果有单调性的话-->我可以二分,反之不然整个区间可以一分为二,我们定义了一个性质,右半边是满足这个性质的,但是左半边不满足二分可以寻找这个性质的边界......
  • AcWing 算法提高课 强连通分量
    1、Tarjan算法求强连通分量: 强连通分量的点可能会向上联通。  维护两个时间戳。 ......
  • G1GC的算法与实现 pdf
    高清扫描版下载链接:https://pan.baidu.com/s/1GO-QAbmrsxH3Qvns1JATyA点击这里获取提取码 ......
  • 算法竞赛进阶指南 0x22 深度优先搜索
    AcWing165.小猫爬山翰翰和达达饲养了N只小猫,这天,小猫们要去爬山。经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。翰翰和达达只好......
  • 算法中的最优化方法01
    算法中的最优化方法0100课程简介优化尽可能用最佳的方式处理一下事项计算机中基于优化的算法多准则控制器的设计模糊建模中的聚类机器人轨迹规划流程工业中的调度......
  • aardio调用百度云人脸识别(api认证机制authorization算法)
    功能:调用百度云识别里的人脸识别api 这里同时分享给需要的人:namespacebaiduimportinet.urlimporttime.zoneimportcrypt.hmacimportcrypt.binstring=........