从零开始学数据结构系列之第二章《字符串暴力匹配》

原理

基本思想

​   从主串的第一个字符开始和子串的第一个字符进行比较，若相等，则继续比较；否则子串退回第一个字符，重新和主串的第二个字符进行比较。反复如此，直到主串完毕。

是什么

​   暴力匹配算法，也称为朴素匹配算法，是一种简单的字符串匹配算法。它的基本思想是从文本串的第一个字符开始，逐个字符地与模式串进行比较，如果匹配失败，则将模式串向右移动一位，再与文本串的下一个字符进行比较，直到找到匹配的子串或者文本串遍历完毕。

​   具体实现时，我们可以使用两个指针 i 和 j 分别指向文本串和模式串的首字符，然后逐个字符地进行比较。如果当前字符匹配成功，则两个指针同时向后移动一位，继续比较下一个字符；否则将模式串的指针 j 向右移动一位，重新从文本串的第 i 个字符开始匹配。

​   暴力匹配算法的时间复杂度为 O(mn)，其中 m 和 n 分别为模式串和文本串的长度。在最坏情况下，需要将模式串移动 n-m+1 次，因此算法的效率较低，不适用于处理大规模的文本匹配问题。但是，暴力匹配算法的实现简单、易于理解，是其他字符串匹配算法的基础，也是一些特殊情况下的最佳选择。

缺点

​   暴力匹配算法的缺点是时间复杂度较高，最坏情况下需要比较 O ( n m ) O(nm)O(nm) 次，其中 n nn 是文本串的长度，m mm 是模式串的长度。当文本串和模式串很长时，算法的效率会非常低下，甚至无法承受。

​   此外，暴力匹配算法只能找到第一个匹配的子串，并不能找到所有匹配的子串。如果需要找到所有匹配的子串，则需要使用其他算法，如 KMP 算法、Boyer-Moore 算法等。

  因此，在实际应用中，暴力匹配算法并不是一个很好的选择，除非文本串和模式串的长度非常小且匹配次数较少。

图解

代码

#include <stdio.h>
#include <stdlib.h>

#define	size 30 

/*
*定义结构体
*/
typedef struct String 
{
	char* data;
	int len;
}String;

/*
*初始化
*s->data=NULL;	防止野指针
*/
String* initString() 
{
	String * s = (String*)malloc(sizeof(String));
	s->data=NULL;
	s->len=0;
	return s;
}

/*
*获取字符
*(char*)malloc(sizeof(char) * (size +1)); 开辟存放字符串的空间，注意字符串结尾有个\0
*		free(temp);
		temp=NULL;
		free(stu->data);
		stu->data=NULL;
		目的是为了释放内存，防止野指针出现
*/
void stringAssign(String* stu) 
{	
	int len=0;	
	char* temp = (char*)malloc(sizeof(char) * (size +1));
	stu->data = (char*)malloc(sizeof(char) * (size +1));
	gets(temp);
	while(*temp && (size -len-1))
	{
		stu->data[len] = *temp;
		len++;
		temp++;
	}
	
	if(len==0)
	{
		free(temp);
		temp=NULL;
		free(stu->data);
		stu->data=NULL;
	}
	stu->len=len;
}
/*
*打印字符串
*/
void printString(String* s) 
{
	int i=0;
	for(;i<s->len;i++)
	{
		printf(i==s->len-1?"%c":"%c->",s->data[i]);
	}
	printf("\r\n");
}

/*
*暴力匹配
*/
void forceMatch(String* master, String* sub) 
{
    int i = 0;
    int j = 0;
	int a=0;
    while (i < master->len && j < sub->len) {
        if (master->data[i] == sub->data[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
		a++;
    }
    if (j == sub->len) {
        printf("在%d个开始重复,共循环了%d\r\n",i-j,a);
    } else {
        printf("force match fail.\n");
    }
}

int main(int argc, char* argv[]) {
    String* s = initString();
	String* s1 = initString();
    stringAssign(s);
	stringAssign(s1);
	printString(s);
    printString(s1);
    forceMatch(s, s1);
    return 0;
}

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》