预览预定义的代码结构：

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
//定义结构体
typedef struct STRING {
	char* st;
	int len;
}STR;

//初始化字符串
STR* initstring() {
	STR* str = (STR*)malloc(sizeof(STR));
	int len = 0;
	char* st = NULL;
	return str;
}

//字符串赋值
void strAssign(STR* str, STR* st) {
	//判断返回的data是否有值,防止野指针的出现
	if (!str->st)
	{
		free(str->st);
	}
	int len = 0;//临时变量储存长度
	char* temp = st;
	while (*temp)//记录长度
	{
		len++;
		temp++;
	}
	if (len == 0) {
		str->st = NULL;
		str->len = 0;
	}
	else {
		temp = st;//因为上面temp依次递增已经轮到了末尾，所以这里再次赋值使其回到原位
		str->len = len;//将len写入
		str->st = (char*)malloc(sizeof(char) * (len + 1));//因为在字符串中最后一位为\0，所以要多一位。
		for (int i = 0; i < len; i++, temp++)//写入字符
		{
			str->st[i] = *temp;
		}
	}
}
//打印字符串
void  printchar(STR*str) 
{
	for (int i = 0; i < str->len; i++)
	{
		printf(i == 0 ? "%c" : "->%c", str->st[i]);
	}
	printf("\n");
}

1. 暴力匹配（BF算法）

首先，暴力匹配需要一个主串和一个字串，，由字串和主串一一对应匹配，当主串与子串不匹配时从这次匹配的下一个开始依次判定匹配，直到匹配到最后一个字符。

示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//暴力匹配代码块
void forceMatch(STR*master,STR*sub) {
	int j=0,i = 0;
	while (i < master->len && j < sub->len) {
		if (master->st[i] == sub->st[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 1;
			j = 0;
		}
	}
	if (j == sub->len) {
		printf("success\n");
	}
	else {
		printf("fail\n");
	}
}

主函数的运行如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int main() {
	STR* string1 = initstring();
	STR* string2 = initstring();
	strAssign(string1,"HELLO");
	strAssign(string2, "ELL");
	printchar(string1);
	printchar(string2);
	forceMatch(string1,string2);

	system("pause");
	return 0;

}

这里我们定义了两个字符串string1，string2.并将其传入到forceMatch中进行匹配。从我们自己的角度可以看出来HELLO中是包含ELL的。那么这里，i和j分别代表string1（主字符串）和string2（子字符串）的匹配时对应的字符位置。然后从住字符串的第一个开始和子字符串中的字符一个跟着一个对比。如果失败就将主字符串移向上一次对比的下一个字符开始重新对比，j继续依次增加，直到j连续到所有字符串都符合或者对比到结尾还未对应时就结束（即不匹配），这里我们匹配就输出success，不匹配就输出fail

此处例子的运行结果如下：（这里用-“>”隔开了）

image-20231119184417467

2. kmp匹配

  • kmp算法相比于暴力算法，没有暴力匹配算法的回溯，可以快速定位匹配。避开了暴力算法的冗杂的回溯寻找过程。
  • kmp算法是一种高效算法，牺牲了一定的空间去保存next数组，提高了匹配效率。相当于保存了索引，引导程序快速找到切入点。
  • kmp算法时间复杂度为（n+m）(n为主串长度，m为副串长度)

next数组：当该字符与主串不匹配后，值对应索引的字符要移动到跟主串不匹配的字符对齐。==next数组存储的为最大公共前后缀+1。==

在代码实现中我们用这种方式获取next数组，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//获取next数组
int* NEXT(STR* str) {
	int* next1 = (int*)malloc(sizeof(int) * str->len);
	int i = 0;
	int j = -1;
	next1[i] = j;
	while (i < str->len - 1) {
		if (j == -1 || str->st[i] == str->st[j]) {
			i++;
			j++;
			next1[i] = j;
		}
		else {
			j = next1[j];
		}
	}
	return next1;
}

那么在匹配时，我们应该是这样操作的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void kmpMatch(STR* master, STR* sub,int*next) {
	int i = 0;
	int j = 0;
	while (i < master->len &&j<sub->len) {
		if (master->st[i] == sub->st[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];
		}
	}
	if (j == sub->len) {
		printf("success!\n");
	}
	else {
		printf("fail!\n");
	}
}

由以上代码我呢可以注意到，与暴力破解最大的不同是，==我们只对j进行操作，并不对i进行操作，也就是不对主串操作。这是kmp匹配和暴力匹配最大的区别==

3.资料参考

【KMP算法精讲（2）——什么是最长公共前后缀？】https://www.bilibili.com/video/BV1hX4y1C73S?vd_source=602097138258a0057a732e44579de1ed

【UP从0到1带你手撕数据结构全集(C语言版)】https://www.bilibili.com/video/BV1W64y1z7jh?p=9&vd_source=602097138258a0057a732e44579de1ed