投稿
  1. 首页
  2. C

【数据结构】第四章 串（2）朴素模式匹配算法、KMP算法（C++）

push•2022-6-14•C•阅读18

【数据结构】第四章 串（2）朴素模式匹配算法、KMP算法（C++）,第1张

目录

4.2_1 朴素模式匹配算法

一、什么是字符串的模式匹配

二、朴素模式匹配算法

（1）使用字符串基本 *** 作来实现

（2）通过数组下标来实现

总结：

4.2_2 KMP算法

一、KMP算法由来

二、朴素模式匹配算法

三、朴素模式匹配算法优化思路

四、如何用代码实现KMP匹配过程

4.2_3 KMP算法_求 next 数组

一、手算

二、KMP算法（next数组）完整代码

4.2_4 KMP算法的进一步优化

一、next 数组的优化思路

二、KMP算法（nextval数组）完整代码

4.2_1 朴素模式匹配算法 一、什么是字符串的模式匹配

在一段文字中搜索某一段内容。

主串：被搜索的字符串。

模式串：想要搜索的内容。

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

* 子串——主串的一部分，一定存在；

模式串——不一定能在主串中找到；

二、朴素模式匹配算法

因为模式串T的长度为6，所以就把主串S中长度为6的字符串与模式串T一一对比。

主串长度为n，模式串长度为m。

朴素匹配模式算法：将主串中所有长度为m的子串依次与模式串对比（最多对比n-m+1个子串），直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

（1）使用字符串基本 *** 作来实现

上一节代码实现中Index(S, T)函数就是用的这种算法。

// (8)求子串。用Sub返回串S的第pos个字符起长度为len的字符串
bool SubString(SString &Sub, SString S, int pos, int len){
	// 子串范围越界
	if(pos+len-1 > S.length){
		return false;
	} 
	// 把S的子串一个个填进Sub字符串里，并给Sub长度赋值 
	for(int i = pos; i < pos+len; i++){
		Sub.ch[i-pos+1]  = S.ch[i];
	}
	Sub.length = len;
	
	return true;
} 

// (9)比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S
（2）通过数组下标来实现

不使用字符串的基本 *** 作，直接通过数组下标实现朴素模式匹配算法。

（1）S[i]与T[j]字符进行比较，看是否匹配

（2）若当前子串匹配失败，则主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置。

i = i - j + 2;

j = 1;

（3）若j > T.length，则当前子串匹配成功，返回当前子串第一个字符的位置（i - T.length）

运行结果：

实现代码：

// 20220605 朴素模式匹配算法

#include
#include
using namespace std;

// 串的静态数组存储
#define MAXLEN 255
typedef struct{
	char ch[MAXLEN];  // 串中字符存储（从下标1开始存） 
	int length;  // 串长度 
}SString;

// 朴素模式匹配
int Index(SString S, SString T){
	int i = 1, j = 1;
	while(i <= S.length && j <= T.length){ 
		cout << "S.ch[i]：" << S.ch[i] << "，T.ch[j]：" << T.ch[j] << endl;
		if(S.ch[i] == T.ch[j]){  // 如果匹配就两个指针后移，让下一个字符开始比较 
			++i;
			++j; 
		}else{
			i = i - j + 2;  // 主串指针回退，退到下一次该匹配的位置 
			j = 1;  // 模式串指针回退，退到第一个字符 
		}
	}
	if(j > T.length){
		cout << "主串中子串位置为：" << i-T.length << endl;
		return i - T.length;  // 匹配成功 
	}else{
		cout << "未在主串中查找到子串位置！" << endl;
		return 0;
	}
} 

// 串的赋值
bool StrAssign(SString &T, string chars){
	T.length = chars.length();
	for(int i = 1; i <= T.length; i++) T.ch[i] = chars[i-1];
	return true;
}

void Printch(SString S){
	for(int i = 1; i <= S.length; i++){
		cout << S.ch[i];
	}
} 

int main(){
	cout << "Hello Madoka!" << endl;
	
	// 两个串的声明 
	SString S, T;
	
	// 两个串赋值，S主串，T子串
	StrAssign(S, "Do you like Madoka?");
	StrAssign(T, "Madoka");
	
	// 输出测试
	cout << "主串值：" << endl;
	Printch(S);
	cout << endl << "主串长度：" << S.length << endl;
	cout << "子串值：" << endl;
	Printch(T);
	cout << endl << "子串长度：" << T.length << endl; 
	
	// 朴素模式匹配
	cout << "子串在主串中的位置为：" << Index(S, T) << endl;
	
	return 0;
}

时间复杂度分析：

设主串长度为n，模式串长度为m，

最坏时间复杂度 = O((n-m+1) m) =  O( ) = O(nm)

* 为什么省掉——因为很多时候主串n的长度远远大于子串m的长度

总结：

4.2_2 KMP算法 一、KMP算法由来

由D.E.Knuth，J.H.Morris和V.R.Pratt提出，因此称为KMP算法。是基于朴素模式匹配算法的一个优化。

二、朴素模式匹配算法

 一旦发现当前这个子串中某个字符不匹配，就只能转而匹配下一个子串（从下一个子串的头部开始）。

三、朴素模式匹配算法优化思路

（1）模式串第6个元素不匹配。主指针i不变，模式串指针j=3。

（2）模式串第5个元素不匹配。主指针i不变，模式串指针j=2。

 （3）模式串第4个元素不匹配。主指针i不变，模式串指针j=2。

  （4）模式串第3个元素不匹配。主指针i不变，模式串指针j=1。

 （5）模式串第2个元素不匹配。主指针i不变，模式串指针j=1。

（6）模式串第1个元素不匹配。主指针i=i+1，模式串指针j=1。

经过优化后，主串指针不再“回溯”。

 

四、如何用代码实现KMP匹配过程

使用 next 数组，next[ i ] 存放当第 i 个元素匹配失败时，模式串指针应该指向的位置，需要针对 next[ 1 ] 单独判断。

next 数组只和相对较短的模式串有关，和长长的主串无关。

KMP 算法就是先根据模式串T，求出 next 数组，再利用 next 数组进行匹配（主串指针不回溯）。

// KMP_对比 
int Index_KMP(SString S, SString T, int next[]){
	// i主串指针，j子串指针 
	int i = 1, j = 1;  // 初始都指向各自的第一个字符位置 
	while(i <= S.length && j <= T.length){
		// 如果当前属于子串第一个字符就不匹配的情况（j==0），或者当前比较字符相同
		if(j == 0 || S.ch[i] == T.ch[j]){  
			++i;  // 各自向后移一位，等待下一次的比较 
			++j;
		}else{
			j = next[j];  // 根据 next 数组进行子串指针j的右移 
		} 
	}
	if(j > T.length){
		return i-T.length;  // 匹配成功 
	}else{
		return 0;
	} 
}

时间复杂度分析：
最坏时间复杂度O(m+n)

求 next 数组时间复杂度 O(m)，

模式匹配过程最坏时间复杂度 O(n)。

4.2_3 KMP算法_求 next 数组 一、手算

next 数组的作用：当模式串的第 j 个字符失配时，从模式串的第 next[j] 个字符开始继续向后匹配。

（1）任何模式串都一样，第 1 个字符不匹配时，只能匹配下一个字符串，因此 next[ 1 ] 可以直接写 0；

（2）任何模式串都一样，第 2 个字符不匹配时，只能匹配下一个字符串，因此 next[ 2 ] 可以直接写 1；

（3）在不匹配位置的前面为分割线，模式串一步步右移，直到“对上”主串之前，j 指针指向第几个，next[ i ] 的值就是几；

二、KMP算法（next数组）完整代码

运行结果：

完整代码：

// 20220605 KMP算法（next数组写法）

#include 
#include 
using namespace std;

// 串的静态数组存储
#define MAXLEN 255
typedef struct{
	char ch[MAXLEN];  // 字符存储在数组里，从下标1开始存 
	int length;  // 串的长度 
}SString;

// next数组全局变量声明
int next[MAXLEN];

// next数组（传入模式串、空next数组） 
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];
		}
	} 
} 

// KMP对比（传入主串、模式串、next数组） 
int Index_KMP(SString S, SString T, int next[]){
	int i = 1, j = 1;  // 指向主串、模式串的两个指针
	
	while(i <= S.length && j <= T.length){
		// 第一个字符就不匹配的情况j==0
		// 或 匹配成功的情况
		if(j == 0 || S.ch[i] == T.ch[j]){
			++i;  // 各自指针后移一位，等待下一位的比较 
			++j;
		}else{
			j = next[j];  // 根据next数组把子串右移 
		} 
	} 
	
	if(j > T.length){
		return i - T.length;  // 匹配成功 
	}else{
		return 0;
	}
} 

// 串的赋值 
bool StrAssign(SString &T, string chars){
	T.length = chars.length();  // 长度
	for(int i = 1; i <= T.length; i++){
		T.ch[i] = chars[i-1];
	}
	return true;
}

// 串的打印
bool Printch(SString S){
	for(int i = 1; i <= S.length; i++){
		cout << S.ch[i]; 
	}
} 
 
int main(){
	// 主串、模式串的声明
	SString S, T;
	
	// 主串、子串的输入、赋值
	StrAssign(S, "Do you like Madoka?");
	StrAssign(T, "Madoka");
	
	// 测试输出
	cout << "主串值为：";
	Printch(S);
	cout << endl; 
	cout << "子串值为：";
	Printch(T);
	cout << endl;
	
	// next 数组
	cout << "子串的next数组为：" << endl;
	get_next(T, next);
	for(int i = 1; i <= T.length; i++){
		cout << next[i] << " ";
	} 
	cout << endl;
	
	// KMP匹配
	cout << "KMP寻找到的子串在主串的位置为：" << Index_KMP(S, T, next) << endl;
	 
	return 0;
}

4.2_4 KMP算法的进一步优化 一、next 数组的优化思路

若初次匹配 S[ 3 ] 与 T[ 3 ] 不匹配，那么 S[ 3 ] 一定不为 'a' ，优化思路是把 next[ 3 ] 直接存 0，跳过 next[ 3 ]。

 同样的情况，当模式串 next[ 5 ] 不匹配时，表示对应的主串 S[ ? ] 也一定不为 'b'，优化思路是把 next[ 5 ] 直接存 1，将主串的该字符与模式串T中的第一个字符开始比较。

优化过后的 next 数组为：

Q：什么样的模式串可以用到 next 数组优化？

A：找到当前匹配失败的字符对应的 next[ x ] 数组存放的数字 y，如果模式串 T 的第 y 号字符与 第 x 号字符相等，就把next[ x ] 数组存放的数字 y 优化成 next[ y ] 数组存放的数字。

练习1：

练习2：

二、KMP算法（nextval数组）完整代码

运行结果如下：

完整代码：

// 20220605 KMP(nextval)

#include 
#include 
using namespace std;

// 串的静态数组存储
#define MAXLEN 255
typedef struct{
	char ch[MAXLEN];  // 字符存储（从下标1开始）
	int length;  // 长度 
}SString; 

// next、nextval数组
int next[MAXLEN];
int nextval[MAXLEN];

// next数组
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];
		}
	}
}

// nextval数组（这里用的是从next数组推出来nextval的写法）
void get_nextval(SString T, int next[]){
	for(int j = 2; j <= T.length; j++){  // 从第二个字符开始遍历 
		if(T.ch[next[j]] == T.ch[j]){  // 判断 当前next[j]存放的数值所对应的字符 与 本身对应的第j个字符是否相等 
			nextval[j] = nextval[next[j]];  // 当前nextval[j]更新成前面与本字符相等的nextval数组的值 
		}else{
			nextval[j] = next[j];
		}
	}
}

// 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){
		return i - T.length;  // 匹配成功 
	}else{
		return 0;
	}
} 

// 串的赋值
bool StrAssign(SString &T, string chars){
	T.length = chars.length();  // 长度 
	for(int i = 1; i <= T.length; i++){  // 字符 
		T.ch[i] = chars[i-1];
	}
	return true;
}

// 串的打印
bool Printch(SString S){
	for(int i = 1; i <= S.length; i++){
		cout << S.ch[i];
	}
} 

int main(){
	// 主串、模式串的声明
	SString S, T;
	
	// 初始化
	StrAssign(S, "Do you like ababaa Madoka?");
	StrAssign(T, "ababaa");
	
	// 输出测试
	cout << "主串值为：";
	Printch(S);
	cout << endl << "子串值为：";
	Printch(T);
	cout << endl;
	
	// nextval数组
	cout << "nextval数组为：" << endl;
	get_next(T, next);
	get_nextval(T, next);
	for(int i = 1; i <= T.length; i++){
		cout << nextval[i] << " ";
	} 
	cout << endl;
	
	// KMP匹配结果
	cout << "模式串在主串中第一次出现的位置为：" << Index_KMP(S, T, nextval); 
	 
	return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/1353659.html

赞 (0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
pushpush一级用户组
00
上一篇 2022-06-14
下一篇2022-06-14

发表评论

登录后才能评论

评论列表（0条）

    保存