【数据结构与算法——C语言】“串操作与算法”之“编写模式匹配算法”

目录

• 1. 实验内容及上机实验所用平台
• • 1.1 实验内容
  • 1.2 实验平台软件
• 2. 设计描述与分析
• • 2.1 流程图
  • 2.2 主要代码段
  • • 2.2.1 BF 算法
    • 2.2.2 KMP 算法
  • 2.3 源代码
  • • 2.3.1 BF 算法
    • 2.3.2 KMP 算法
• 4. 调试过程
• • 4.1 BF 算法
  • 4.2 KMP 算法
• 5. 实验总结

1. 实验内容及上机实验所用平台

1.1 实验内容

【问题描述】
编写模式匹配算法，这里编写了 BF 算法和改进的 KMP 算法。
【输入形式】

主串s	模式串t
“aaaabcaaaaabaaaaabc”	“aaaabaaaaabc”
“ababcabcacbab”	“abcac”
“aaabaaaab”	“aaaab”
“abcaabbabcabaacbacba”	“abcabaa”
“abcdabcdabcda”	“abcda”
“aabcaabababaca”	“ababac”
“abcdabcdabcdc”	“abcdc”
“abcabcabccddab”	“abcd”
“aabaabaabacaabaabaabacaabaabaabac”	“aabaabaac”
“a a a a a b”	“a a a b”

【输出形式】
是否匹配，并输出模式串首字符在主串中的位置。

1.2 实验平台软件

Dev-C++.

2. 设计描述与分析

2.1 流程图

2.2 主要代码段

2.2.1 BF 算法

int BF(string s, string t) {
	int i = 0, j = 0;
	while(i < s.length() && j < t.length()) {
		if (s[i] == t[j]) {	// 若字符相同，i、j 后移 
			i++; j++;
		}
		else {	// 否则 i 回到本轮开始的下一个字符，指向串 t 的下标 j 置为 0 
			i = i + 1 - j;
			j = 0;
		}
	}
	if (j == t.length()) return i - t.length();	// 若串 t 遍历完了，表示匹配成功，输出串 t 首位置在串 s 的位置 
	else return -1;	// 否则没有匹配成功 
}

2.2.2 KMP 算法

void getnextval(string t, int *nextval) {	// 求模式串 t 的nextval 
	int j = 0, k = -1;
	nextval[0] = -1;	// 第一个 nextval 默认为 -1
	while (j < t.length()) {
		if (k == -1 || t[j] == t[k]) {	// 若 k 为 -1 或者字符相同，j、k 后移 
			j++; k++;
			if (t[j] != t[k]) nextval[j] = k;	// 字符不同时，nextval 置为 k 
			else nextval[j] = nextval[k];	// 字符相同时，采用同一个 nextval 
		}
		else k = nextval[k];	// 字符不同时，k 回退 
	}
}

int KMP(string s, string t) {
	int len_s = s.length(), len_t = t.length(), *nextval = new int[len_t], i = 0, j = 0;
	getnextval(t, nextval);
	while(i < len_s && j < len_t) {
		if (j == -1 || s[i] == t[j]) {	// 若 j 为 -1 或者字符相同，i、j 后移 
			i++; j++;
		}
		else j = nextval[j];	// 若字符不同，则 j 回退，i 不变 
	}
	if (j >= len_t) return i - len_t;	// 若串 t 遍历完了，表示匹配成功，输出串 t 首位置在串 s 的位置 
	else return -1;	// 否则没有匹配成功 
}

2.3 源代码

需要先在源代码目录下新建 in.txt 文件，在此文件下输入要测试的数据。

2.3.1 BF 算法

#include <iostream>
#include <string>
using namespace std;

int BF(string s, string t) {
	int i = 0, j = 0;
	while(i < s.length() && j < t.length()) {
		if (s[i] == t[j]) {	// 若字符相同，i、j 后移 
			i++; j++;
		}
		else {	// 否则 i 回到本轮开始的下一个字符，指向串 t 的下标 j 置为 0 
			i = i + 1 - j;
			j = 0;
		}
	}
	if (j == t.length()) return i - t.length();	// 若串 t 遍历完了，表示匹配成功，输出串 t 首位置在串 s 的位置 
	else return -1;	// 否则没有匹配成功 
}

int main() {
	freopen("in.txt", "r", stdin);
	string s, t, str, target1 = "“", target2 = "”";
	int pos1, n1, pos2, n2, i = 0, val;
	cout << "\t第1题 - 编写模式匹配算法（BF算法）\n\n\n";
	cout << "--------------------------------------------------------------\n\n";
	while (getline(cin, str)) {
		printf("[%d] 样例输入：%s\n\n", ++i, str.c_str());
		
		// 截取主串 s 
		pos1 = str.find(target1);	// 找第一个左引号下标 
		pos2 = str.find(target2);	// 找第一个右引号下标 
		s = str.substr(pos1+2, pos2-2);	// 返回主串 s 
		// 将主串的引号删除，以便于截取模式串 t 
		n1 = target1.size();	// 取得左引号长度 
		str = str.erase(pos1, n1);	// 删除第一个左引号 
		pos2 = str.find(target2);	// 由于删除了第一个左引号，需要重新找第一个右引号下标 
		n2 = target2.size();	// 取得右引号长度 
		str = str.erase(pos2, n2);	// 删除第一个右引号 
		// 截取模式串 t 
		pos1 = str.find(target1);	// 找第二个左引号下标 
		pos2 = str.find(target2);	// 找第二个右引号下标 
		t = str.substr(pos1+2, pos2-pos1-2);	// 返回模式串 t 
		
		val = BF(s, t);
		printf("[%d] 样例输出：", i);
		if (val != -1) printf("匹配成功！模式串首字符在主串中的位置下标是：%d\n", val);
		else printf("匹配不成功！\n");
		cout << "\n==============================================================\n";
	}
	cout << "10个样例输出完毕！\n\n";
	freopen("CON", "r", stdin);	// 为了可直接查看exe可执行文件，需要将权限返回键盘 
	system("pause");
	return 0;
}

2.3.2 KMP 算法

#include <iostream>
#include <string>
using namespace std;

void getnextval(string t, int *nextval) {	// 求模式串 t 的nextval 
	int j = 0, k = -1;
	nextval[0] = -1;	// 第一个 nextval 默认为 -1
	while (j < t.length()) {
		if (k == -1 || t[j] == t[k]) {	// 若 k 为 -1 或者字符相同，j、k 后移 
			j++; k++;
			if (t[j] != t[k]) nextval[j] = k;	// 字符不同时，nextval 置为 k 
			else nextval[j] = nextval[k];	// 字符相同时，采用同一个 nextval 
		}
		else k = nextval[k];	// 字符不同时，k 回退 
	}
}

int KMP(string s, string t) {
	int len_s = s.length(), len_t = t.length(), *nextval = new int[len_t], i = 0, j = 0;
	getnextval(t, nextval);
	while(i < len_s && j < len_t) {
		if (j == -1 || s[i] == t[j]) {	// 若 j 为 -1 或者字符相同，i、j 后移 
			i++; j++;
		}
		else j = nextval[j];	// 若字符不同，则 j 回退，i 不变 
	}
	if (j >= len_t) return i - len_t;	// 若串 t 遍历完了，表示匹配成功，输出串 t 首位置在串 s 的位置 
	else return -1;	// 否则没有匹配成功 
}

int main() {
	freopen("in.txt", "r", stdin);
	string s, t, str, target1 = "“", target2 = "”";
	int pos1, n1, pos2, n2, i = 0, val;
	cout << "\t第1题 - 编写模式匹配算法（KMP算法）\n\n\n";
	cout << "--------------------------------------------------------------\n\n";
	while (getline(cin, str)) {
		printf("[%d] 样例输入：%s\n\n", ++i, str.c_str());
		
		// 截取主串 s 
		pos1 = str.find(target1);	// 找第一个左引号下标 
		pos2 = str.find(target2);	// 找第一个右引号下标 
		s = str.substr(pos1+2, pos2-2);	// 返回主串 s 
		// 将主串的引号删除，以便于截取模式串 t 
		n1 = target1.size();	// 取得左引号长度 
		str = str.erase(pos1, n1);	// 删除第一个左引号 
		pos2 = str.find(target2);	// 由于删除了第一个左引号，需要重新找第一个右引号下标 
		n2 = target2.size();	// 取得右引号长度 
		str = str.erase(pos2, n2);	// 删除第一个右引号 
		// 截取模式串 t 
		pos1 = str.find(target1);	// 找第二个左引号下标 
		pos2 = str.find(target2);	// 找第二个右引号下标 
		t = str.substr(pos1+2, pos2-pos1-2);	// 返回模式串 t 
		
		val = KMP(s, t);
		printf("[%d] 样例输出：", i);
		if (val != -1) printf("匹配成功！模式串首字符在主串中的位置下标是：%d\n", val);
		else printf("匹配不成功！\n");
		cout << "\n==============================================================\n";
	}
	cout << "10个样例输出完毕！\n\n";
	freopen("CON", "r", stdin);	// 为了可直接查看exe可执行文件，需要将权限返回键盘 
	system("pause");
	return 0;
}

4. 调试过程

4.1 BF 算法

注：下标从 0 开始计算。

最后一个样例的空格也占一个字符位哦~

4.2 KMP 算法

5. 实验总结

本次实验让我对 string 容器有了更深的认识，学会了通过 string 容器的成员函数截取字符串，解决了上一次实验遗留的问题，也让我加深了 BF 算法和 KMP 算法的理解。