1. 首页
  2. 文章中心
  3. 算法

实现顺序串的各种模式匹配算法实现顺序串的各种模式匹配算法

119 阅读 0 评论
我是靠谱客的博主 诚心咖啡，这篇文章主要介绍实现顺序串的各种模式匹配算法实现顺序串的各种模式匹配算法，现在分享给大家，希望可以做个参考。

实现顺序串的各种模式匹配算法

目的：掌握串的模式匹配算法（即BF和KMP算法）设计。

内容：编写一个程序，实现顺序串的各种模式匹配运算，并在此基础上完成以下功能。
（1）：建立目标串s="abcabcdabcdeabcdefabcdefg"和模式串t=“abcdeabcdefab”。
（2）：采用简单匹配算法求t在s中的位置。
（3）：由模式串t求出next数组值和nextval数组值。
（4）：采用KMP算法求t在s中的位置。
（5）：采用改进的KMP算法求t在s中的位置。

建立目标串：

一般不建议如此操作。

复制代码
1
2
3
4
5
6
7
8
void StrAssign(Str& S, char* s)	//生成顺序串
{
	int i;
	for (i = 0; s[i] != ''; i++); //计算字符串长度
	S.length = i;	//顺序串长度
	S.data = s;		//顺序串内容
}

简单匹配算法（BF）：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int SubStr(Str S, Str T) //BF算法
{
	int i, j;
	for (i = 0; i < S.length; i++) {
		for (j = 0; j < T.length; j++) {
			if (S.data[i + j] != T.data[j])
				break;	//当目标串与模式串不匹配时结束内循环，对下一个子串进行匹配
		}
		if (j >= T.length)	//当模式串全部扫描完成说明模式串已经找到了匹配的位置
			return (i+1);	//返回匹配的位置
	}
	return -1;
}

next数组：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void GetNext(Str T, int*& next)
{
	int i, j;
	i = 0;
	j = -1;
	next = (int*)malloc(T.length * sizeof(int));
	while (next == NULL) {	//预防空间申请失败
		next = (int*)malloc(T.length * sizeof(int));
	}
	next[0] = -1;
	while (i < T.length) {
		if (j == -1 || T.data[i] == T.data[j]) {
			i++;
			j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

nextval数组：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void GetNextval(Str T, int*& nextval)
{
	int i, j;
	i = 0;
	j = -1;
	nextval = (int*)malloc(T.length * sizeof(int));
	while (nextval == NULL) {	//预防空间申请失败
		nextval = (int*)malloc(T.length * sizeof(int));
	}
	nextval[0] = -1;
	while (i < T.length) {
		if (j == -1 || T.data[i] == T.data[j]) {
			i++;
			j++;
			if (T.data[i] != T.data[j])
				nextval[i] = j;
			else
				nextval[i] = nextval[j];
		}
		else
			j = nextval[j];
	}
}

KMP算法：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int KMP(Str S, Str T, int* N)
{
	//S为目标串，T为模式串，N为特征数组
	int i, j;
	i = j = 0;
	while (i < S.length && j < T.length) {
		if (j == -1 || S.data[i] == T.data[j]) {
			i++;
			j++;
		}
		else
			j = N[j];	//i不变，j后退
	}
	if (j >= T.length)
		return (i+1-T.length);	//返回匹配的位置
	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
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<stdio.h>
#include<stdlib.h>

typedef struct String {	//定义顺序串结构体
	char* data;		//数据指针
	int length;		//顺序串长度
}Str;

void StrAssign(Str&, char*);	//生成顺序串
int SubStr(Str, Str);			//BF算法
void GetNext(Str, int*&);		//求next数组
void GetNextval(Str, int*&);	//求nextval数组
int KMP(Str, Str, int*);		//KMP算法

int main(int argc, const char* argv[])
{
	char s[] = "abcabcdabcdeabcdefabcdefg";
	char t[] = "abcdeabcdefab";
	Str S, T;
	int i,idx;	//记录模式串在目标串中的位置
	int* next = NULL, * nextval = NULL; //next数组，nextval数组
	//建立目标串和模式串
	StrAssign(S, s);
	StrAssign(T, t);
	printf("简单匹配的结果（从1开始）：n");
	idx = SubStr(S, T);
	if (idx != -1) {
		printf("匹配成功，位置为%d。n", idx);
	}
	else {
		printf("匹配失败。n");
	}
	GetNext(T, next);
	printf("next数组：n");
	for (i = 0; i < T.length; i++) {
		printf("%dt", next[i]);
	}
	printf("n");
	GetNextval(T, nextval);
	printf("nextval数组：n");
	for (i = 0; i < T.length; i++) {
		printf("%dt", nextval[i]);
	}
	printf("n");
	printf("使用KMP的结果（从1开始）：n");
	idx = KMP(S, T, next);
	if (idx != -1) {
		printf("匹配成功，位置为%d。n", idx);
	}
	else {
		printf("匹配失败。n");
	}
	printf("使用改进KMP的结果（从1开始）：n");
	idx = KMP(S, T, nextval);
	if (idx != -1) {
		printf("匹配成功，位置为%d。n", idx);
	}
	else {
		printf("匹配失败。n");
	}
	return 0;
}
void StrAssign(Str& S, char* s)	//生成顺序串
{
	int i;
	for (i = 0; s[i] != ''; i++); //计算字符串长度
	S.length = i;	//顺序串长度
	S.data = s;		//顺序串内容
}
int SubStr(Str S, Str T) //BF算法
{
	int i, j;
	for (i = 0; i < S.length; i++) {
		for (j = 0; j < T.length; j++) {
			if (S.data[i + j] != T.data[j])
				break;	//当目标串与模式串不匹配时结束内循环，对下一个子串进行匹配
		}
		if (j >= T.length)	//当模式串全部扫描完成说明模式串已经找到了匹配的位置
			return (i+1);	//返回匹配的位置
	}
	return -1;
}
void GetNext(Str T, int*& next)
{
	int i, j;
	i = 0;
	j = -1;
	next = (int*)malloc(T.length * sizeof(int));
	while (next == NULL) {	//预防空间申请失败
		next = (int*)malloc(T.length * sizeof(int));
	}
	next[0] = -1;
	while (i < T.length) {
		if (j == -1 || T.data[i] == T.data[j]) {
			i++;
			j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}
void GetNextval(Str T, int*& nextval)
{
	int i, j;
	i = 0;
	j = -1;
	nextval = (int*)malloc(T.length * sizeof(int));
	while (nextval == NULL) {	//预防空间申请失败
		nextval = (int*)malloc(T.length * sizeof(int));
	}
	nextval[0] = -1;
	while (i < T.length) {
		if (j == -1 || T.data[i] == T.data[j]) {
			i++;
			j++;
			if (T.data[i] != T.data[j])
				nextval[i] = j;
			else
				nextval[i] = nextval[j];
		}
		else
			j = nextval[j];
	}
}
int KMP(Str S, Str T, int* N)
{
	int i, j;
	i = j = 0;
	while (i < S.length && j < T.length) {
		if (j == -1 || S.data[i] == T.data[j]) {
			i++;
			j++;
		}
		else
			j = N[j];	//i不变，j后退
	}
	if (j >= T.length)
		return (i+1-T.length);	//返回匹配的位置
	else
		return -1;
}

最后

以上就是诚心咖啡最近收集整理的关于实现顺序串的各种模式匹配算法实现顺序串的各种模式匹配算法的全部内容，更多相关实现顺序串内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(79)

相关文章

Django fullcalendar.js 日历事件 添加/删除/修改
Django fullcalendar.js 日历事件 添加/删除/修改
日历 fullCalendar 整合农历
日历 fullCalendar 整合农历
FullCalendar 学习笔记——简单的节假日设置
FullCalendar 学习笔记——简单的节假日设置
顺序串的实现(插入、截取、匹配)
顺序串的实现(插入、截取、匹配)
实现顺序串的各种模式匹配算法实现顺序串的各种模式匹配算法
实现顺序串的各种模式匹配算法实现顺序串的各种模式匹配算法
串的模式匹配算法之BF算法
串的模式匹配算法之BF算法
问题 A: 求最长公共子串（串）
问题 A: 求最长公共子串（串）
模式匹配-BF算法
模式匹配-BF算法

评论列表共有 0 条评论

立即
投稿
返回
顶部