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

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

1.1 实验内容

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

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

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;	// 否则没有匹配成功 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;	// 否则没有匹配成功 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2.3 源代码

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

2.3.1 BF 算法

#include 
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

2.3.2 KMP 算法

#include 
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

4. 调试过程

4.1 BF 算法

注：下标从 0 开始计算。

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

4.2 KMP 算法

5. 实验总结

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