串的模式匹配算法(超详细)

这篇具有很好参考价值的文章主要介绍了串的模式匹配算法(超详细)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 简单的模式匹配算法

思想: 将主串中所有长度为m的子串依次与模式串对比,直到找到一个完全匹配的子串或所有子串都不匹配为止。
串的模式匹配算法(超详细)

具体代码展示:
1)串的初始化工作

#include<stdio.h>
#define MAXLEN 255  //预定义最大串长

typedef struct {
	char ch[MAXLEN];//每一个分量存储一个字符
	int length;//串的实际长度
}SString;

// 字符串下标从1开始记录,将ch[0]设置为‘\0’ 
SString createString() {
	SString str;
	str.ch[0] = '\0';
	str.length = 0;
	return str;
}

//赋值操作
void StrAssign(SString& S, char chars[])//生成串S
{
	int i = 0;
	while (chars[i] != '\0')
	{
		//第一个位置不用
		S.ch[i+1] = chars[i];//将字符串常量的值赋值给S
		i++;
	}
	S.length = i+1;
}

//打印串
void PrintString(SString S) {
	if (S.length == 0) {
		printf_s("当前串为空");
	}
	else {
		for (int i = 1; i < S.length; i++) {
			printf_s("%c", S.ch[i]);
		}
		printf_s("\n");
	}
}

2)简单模式匹配算法实现

int Index(SString S, SString T) {
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length) {
		//相等则指针+1
		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 2;//主串指针退回到当前指针的下一个位置
			j = 1;//模式串指针退回到第一个位置
		}
		//放在这里判断是为了返回第一个匹配的子串位置,
		//T的长度是实际长度+废弃的第一个位置长度,所以这里减一
		//说明匹配完成,指向T的最后一个元素的下一个位置
		if (j > T.length - 1) {
			return i - T.length + 1;
		}
	}
	return 0;
}

3)主函数调用

int main(){
	SString S=createString(), T=createString();
	char ch1[] = { "aaabaabcaabdabacaabc" };
	char ch2[] = { "aabc" };
	StrAssign(S, ch1);
	StrAssign(T, ch2);
	printf_s("S串元素为:");
	PrintString(S);
	printf_s("T串元素为:");
	PrintString(T);
	printf_s("----------------------------\n");
	printf_s("简单模式匹配算法:\n");
	printf_s("子串在主串位置为:%d", Index(S, T));
}

4)结果展示
串的模式匹配算法(超详细)

注意:子串匹配的是在主串中首次出现的,在所给例子中,子串出现了两次,但是记录的位置是第一次出现的位置。

2 KMP算法

简单模式匹配算法: 当子串的某一字符与主串对应的字符不匹配时,主串的指针会回溯到扫描第一个位置的下一个位置,子串的指针也会回溯到第一个位置,然后重新匹配。但是没必要去比较后面的某些位置,因为在主串中,匹配失败的那个字符肯定不是b,所以下一次指针位置应该为3,而不是2,如下图所示。
串的模式匹配算法(超详细)

所以,也就引出了KMP算法,即将子串的指针位置组成一个next数组,这样就极大地减少比较的次数。next[i]的含义是在第i个字符与主串发生失配时,则跳到字串的next[i]位置重新与主串当前位置进行比较。
比如主串为:abacaabefc,子串为aab,则next数组为0,1,2。手算可以推出来的,并且要注意的是next[1]肯定等于0,为什么?因为当子串的第一个字符匹配失败时,那肯定转到第二个位置继续匹配。

具体代码展示:

1)next数组代码求解过程如下(不作过多讲解)

//求next数组
//next[1]为0,next[2]为1
void get_next(SString T, int next[]) {
	int i = 1, j = 0;
	next[1] = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) {
			i++;
			j++;
			next[i] = j;
		}
		else {
			j = next[j];
		}
	}
}

2)KMP算法实现

int Index_KMP(SString S, SString T, int next[]) {
	int i = 1, j = 1;
	while (i <= S.length&&j <= T.length) {
		if (j == 0 || S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];//确定模式串的指针位置
		}
		//匹配成功
		if (j > T.length-1) {
			return i - T.length+1;
		}
	}
	return 0;
}

3)主函数调用

int main(){
	SString S=createString(), T=createString();
	char ch1[] = { "abacaabefc" };
	char ch2[] = { "aab" };
	StrAssign(S, ch1);
	StrAssign(T, ch2);
	printf_s("S串元素为:");
	PrintString(S);
	printf_s("T串元素为:");
	PrintString(T);
	printf_s("----------------------------\n");
	printf_s("简单模式匹配算法:\n");
	printf_s("子串在主串位置为:%d", Index(S, T));
	printf_s("\n----------------------------\n");
    printf_s("KMP算法:\n");
	int next[10] = { -1 };//第一个值弃用
	get_next(T, next);
	printf_s("next数组元素为:");
	for (int i = 1; i < T.length;i++) {
		printf_s("%d ", next[i]);
	}
	printf_s("\n子串在主串位置为:%d", Index_KMP(S, T,next));
}

4)运行结果
串的模式匹配算法(超详细)

3 KMP算法改进

KMP算法问题: 当子串’aaaab’与’aaabaaaab’匹配时,当i=4,j=4时,子串与主串匹配失败,用之前的next数组还需要和S4和P3、S4和P2、S4和P1比较,显然没有意义。问题就出在Pj=Pnext[j]上,因为当Pj≠Sj时,下次匹配的必然是Pnext[j]和Sj比较,如果Pj=Pnext[j],相当于重复匹配相同字符,那怎么办,可以继续递归,将next[j]修改为next[next[j]]直至两者不相等为止。

具体代码实现:
1)next数组优化

//求next数组优化,匹配失败的那个位置的字符肯定不是当前匹配子串的字符
void get_nextval(SString T, int nextval[]) {
	int i = 1, j = 0;
	nextval[1] = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) {
			i++;
			j++;
			if (T.ch[i] != T.ch[j]) {
				nextval[i] = j;
			}
			else {
				nextval[i] = nextval[j];
			}
		}
		else {
			j = nextval[j];
		}
	}
}

2)主函数调用

int main(){
	SString S=createString(), T=createString();
	char ch1[] = { "aaabaaaab" };
	char ch2[] = { "aaaab" };
	StrAssign(S, ch1);
	StrAssign(T, ch2);
	printf_s("S串元素为:");
	PrintString(S);
	printf_s("T串元素为:");
	PrintString(T);
	printf_s("----------------------------\n");
	printf_s("简单模式匹配算法:\n");
	printf_s("子串在主串位置为:%d", Index(S, T));
	printf_s("\n----------------------------\n");
	printf_s("KMP算法:\n");
	int next[10] = { -1 };//第一个值弃用
	get_next(T, next);
	printf_s("next数组元素为:");
	for (int i = 1; i < T.length;i++) {
		printf_s("%d ", next[i]);
	}
	printf_s("\n子串在主串位置为:%d", Index_KMP(S, T,next));
	printf_s("\n----------------------------\n");
	get_nextval(T, next);
	printf_s("nextval数组元素为:");
	for (int i = 1; i < T.length; i++) {
		printf_s("%d ", next[i]);
	}
	printf_s("\n子串在主串位置为:%d\n", Index_KMP(S, T, next));
	return 0;
}

3)运行结果
串的模式匹配算法(超详细)文章来源地址https://www.toymoban.com/news/detail-415626.html

4 时间复杂度比较

  • 简单模式匹配算法: 最坏复杂度为O(mn)
  • KMP算法: 最坏时间复杂度为O(m+n)
    其中求next数组时间复杂度为O(m)
    模式匹配过程中最坏时间复杂度为O(n)

到了这里,关于串的模式匹配算法(超详细)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构—串的详细解释(含KMP算法)

    1.1串的定义 串:串是由零个或多个字符组成的有限序列,又叫字符串(其的存储结构包含顺序表存储、单链表存储的形式。) 一般记为s=\\\"a1a2a3....an\\\"(n=0),其中,s是串的名称,用双引号(也可以使用单引号)括起来的字符序列是串的值,注意引号不是串的内容。ai(i=i=n)可以是字母、

    2023年04月09日
    浏览(45)
  • 【flink番外篇】13、Broadcast State 模式示例-简单模式匹配(1)

    一、Flink 专栏 Flink 专栏系统介绍某一知识点,并辅以具体的示例进行说明。 1、Flink 部署系列 本部分介绍Flink的部署、配置相关基础内容。 2、Flink基础系列 本部分介绍Flink 的基础部分,比如术语、架构、编程模型、编程指南、基本的datastream api用法、四大基石等内容。 3、

    2024年01月19日
    浏览(62)
  • 【Java】BF算法(串模式匹配算法)

    BF算法,即 暴力算法 ,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个与模式串T的第一个字符串进行匹配,若相等,则继续比较S的第二个字符和T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果, BF算

    2024年02月11日
    浏览(35)
  • 匹配模式BF算法

    题目:疫情暴发,专家发现了一种新型环状病毒,这种病毒的DNA序列是环状的,而人类的DNA序列是线性的。专家把人类和病毒的DNA表示为字母组成的字符串序列,如果在某个患者的DNA中发现这种环状病毒,说明该患者已被感染病毒,否则没有感染。例如:病毒的DNA为“aabb”,

    2024年02月11日
    浏览(37)
  • 7-17 KMP模式匹配算法

    给定主串s和模式串p,编写程序使用KMP算法进行模式匹配,计算p在s中出现的首位置,若p不在s中则输出−1。字符串下标从0开始。 输入格式: 输入为2行,第1行为主串s,第2行为模式串p。主串和模式串长度不超过105。 输出格式: 输出为2行,第1行为3个整数,表示分别在模式串

    2024年04月23日
    浏览(54)
  • 4.2.1朴素模式匹配算法

    什么是字符串的模式匹配:  从这段字符串里面搜索内容,被搜索的字符串我们称之为主串。     也可能匹配不到            主串长度为n,模式串长度为m。 朴素模式匹配算法:将主串中所有长度为m的字串依次与模式串对比,直到找到一个完全匹配的字串或所有的字串都

    2023年04月25日
    浏览(27)
  • 【数据结构】朴素模式匹配 & KMP算法

    🌈 自在飞花轻似梦,无边丝雨细如愁 🌈   🌟 正式开始学习数据结构啦~此专栏作为学习过程中的记录 🌟 子串的定位操作通常称为串的模式匹配,它求的是模式串在主串中的位置,而朴素模式匹配就是一种不断移动主串指针,每一次都和模式串依次进行比较的暴力求解方法

    2024年02月16日
    浏览(45)
  • 【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

      字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作: S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=\\\'\\\'a_{0} a_{1}…a_{n-1}\\\'\\\' S = ′′ a 0 ​ a 1 ​ … a n − 1 ′′ ​   其中S是串名,引号中

    2024年02月05日
    浏览(75)
  • 用栈实现括号匹配算法(超详细,超易懂)

     首先我们要明白栈是如何实现这个算法的,在实现算法的过程当中, 栈的作用就是储存左括号,例如储存\\\"[\\\" \\\"}\\\"  \\\'(\\\" 这三种左括号 在程序当中,首先遍历传入的算数组,剔除一些其他的数字,在这里只比较左右括号,然后先将左括号储存到栈当中,例如(((( ] ] ],先将

    2024年02月06日
    浏览(43)
  • C#,字符串匹配(模式搜索)Sunday算法的源代码

    Sunday算法是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。 核心思想:在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。 Sunday算法思想跟

    2024年01月23日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包