KMP算法是暴力匹配算法的改进,相比于暴力匹配,KMP的主串指针不回溯,从而降低了时间复杂度.

详细的KMP算法图解及其原理可以参考视频

第06周01–第4章串、数组和广义表1-4.1串的定义_哔哩哔哩_bilibili


最浅显易懂的 KMP 算法讲解_哔哩哔哩_bilibili

以下是具体代码实现:

首先要加入两个头文件#include <stdio.h>和#include <stdlib.h>

1.定义字符串结构体变量

typedef struct String
{
	char *data;
	int len;
}String;

2.初始化结构体变量


第06周01–第4章串、数组和广义表1-4.1串的定义_哔哩哔哩_bilibili

String *initString()
{
	String *s = (String *)malloc(sizeof(String));
	s->data = NULL;
	s->len = 0;
	return s;
}

3.字符串写入结构体

void stringAssign(String *s,char *data)
{
	if(s->data)//判断结构体是否已经存在数据 
		free(s->data);
	int len = 0,i = 0,j = 0;//len表示字符串长度 
	char *temp = data;//将字符串首地址传送给temp保存 
	while(data[i])//查找字符串的长度 
		data[i++];
	len = i;
	if(len==0)//判断字符串是否为空 
	{
		s->data = NULL;
		s->len = 0;
	}
	else
	{
		s->data = (char *)malloc(sizeof(char)*len);//向结构体中申请与字符串长度相同的内存空间 
		s->len = len;//更改结构体中的字符串长度标识 
		for(i=0;i<len;i++)
		{
			s->data[i] = temp[i];//按位赋值写入 
		}		
	}

}

4.next数组求解

int *getNext(String *s)
{
	int *next = (int *)malloc(sizeof(int)*s->len);//申请一个和字符串s相同长度的内存空间用来存放next数组 
	int i = 0;//用i标识串的索引 
	int j = -1;//用j标识next的初始值 
	next[i] = j;//next初始值为-1 
	while(i<s->len-1)
	{/*(难点)第一种情况:j=-1,则表明i与j所指的位置元素不匹配,索引串i值加一,j值加一为0,将0赋值给数组的第i个位置
	第二种情况:索引i与索引j指向的元素相等,此时i++,j++,将相同的个数j赋值给next数组.(建议自己画图推理加深理解)*/
		if(j==-1||s->data[i]==s->data[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
	return next; 
}

5.KMP匹配

void kmpMatch(String *s,String *r,int *next)
{
	int i = 0;//指向主串的移动标识 
	int j = 0;//指向匹配串的移动标识 
	while(i<s->len&&j<r->len)//逐个字符匹配,直到两个中的其中一个匹配结束退出循环 
	{
		if(j==-1||s->data[i]==r->data[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if(i==s->len)
		printf("匹配成功!\n");
	else
		printf("匹配失败!\n");
}

6.遍历输出字符串

void printString(String *s)
{
	int i;
	for(i=0;i<s->len;i++)
		printf("%c ",s->data[i]);//按照结构体中的len标量,依次输出字符 
	printf("\n");
}

7.遍历输出next数组

void printNext(int *next,int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		printf("%d ",next[i]+1);
	}
	printf("\n");
}

8.主函数验证

int main()
{
	String *s = initString();//初始化 
	String *r = initString();
	char *str1 = "HELLO";
	char *str2 = "LLO";
	stringAssign(s,str1);//验证写入
	stringAssign(r,str2);
	int *next = getNext(r);//验证求解next数组 
	printNext(next,r->len);//验证遍历输出next数组 
	printString(s);
	printString(r);//验证遍历输出
	kmpMatch(s,r,next); 
	return 0;
}