字符串：你看的懂的KMP算法（带验证）

落日映苍穹つ 2022-05-31 01:45 108阅读 0赞

# 前言 #

**KMP算法可以说说许多学习算法的同学的第一道坎，要么是领会不到KMP算法的思想，要么是知道思想写不出代码，网上各种查找**。关于算法的书籍上也都有KMP算法的实现，可为啥自己写不出来呢？博主看得**大话数据结构**上的分析，**书上的代码都比较精简，但是不易理解 ，跟着代码思路走结果也是对的**。那么我们为啥我们不可以多写几行代码 更加容易理解呢。**博主今天就用普通程序员的思路 去写KMP算法 采用C语言实现，虽然代码可能会多那么几行，如果你能看懂，那我也就很高兴了，如果看不懂 请看大话数据结构中KMP的实现领略其思想 然后自己实现代码没有必要和书上一模一样**。**博主写的KMP算法是结合之前写的[字符串：BF算法][BF]。程序代码可以循环运行进行测试**。

# KMP算法介绍 #

**KMP算法是一种改进的字符串匹配算法**，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。**KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的**。**具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息**。时间复杂度O(m+n)。

# KMP算法思路 #

举个简单先说明KMP思想

主串**abcdefgab** 子串**abcdex**，我们采用BF算法 当比较到字符x和d时候发现相等，这是主串回溯到字符b 又和 子串abcdex进行比较 然后c...e 和子串abcdex进行比较。我们明显知道，主串的abcde已经和子串的abcde相等了，而且abcde字符之间互不相等！那么主串中b c 有必要 再次和子串abcd进行比较么，没有必要，因为 主串abcde和子串abcde匹配 而且他们 之间又是互不相等 所以没有 b...e和子串进行比较了。只需要步骤①和步骤⑥ 请看下图（大话数据结构上的图）

![SouthEast][]

如果在不相等的字符前面有重复的字符串的情况怎样呢？主串**abcabcabc**和子串**abcabx** 是不是应该和下图一样呢？仔细想一想是不是呢，领悟...，子串回溯到不相等字符前 的 重复字符串的后面。

![SouthEast 1][]

**所以我们回溯的重点是子串而不是主串，尤其是当我们子串有大量不重复字符且长度越长，节省的比较次数越多**。

KMP算法和BF算法和核心区别就是遇到不相等的字符串 主串和子串的回溯问题，BF算法遇到不相等字符主串回溯到之前开头比较的第一位字符的下一位 子串回溯到第一位 会进行大量没有必要的比较，而KMP算法会根据子串中字符情况进行比较。

# next 数组推导 #

**下面我们就进行子串中每个字符回溯位置的推导，将子串每个字符回溯的位置放在一个next数组中，字符串格式采用书上推荐的格式sub\_str\[0\]存放子串长度，sub\_str\[1\]开始放字符，那么我们的next数组同样也是从\[1\]开始放字符对应的回溯位置**。比如说我们匹配的子串是ababaaaba，每个字符的next值就是他前缀表达式和后缀表达式相等元素个数+1。

子串下标123456789 123456789

子串ababaaaba aaaaaaaab

next值     011234223 012345678

注意 **next\[1\] = 0 next\[2\] = 1 这是不变的**，**然后从第3位字符开始，我们就要进行前缀后缀字符重复的计算了**，重复1位next\[\]值是2重复2位next\[\]值是3 依次类推，当比较到不等字符时 最后一位和第一位重新比较如果还是不等那next值就是1，否则就是2。总感觉描述代码实现不清楚，下面还是看代码吧。

/*
    获取子串的next数组
    没有优化的的next数组
    */
    int* NextKMP1(uchar* sub_str)
    {
    	int subLen = sub_str[0];
    	int* next = (int*)malloc(sizeof(int)*(subLen + 1));
    	next[1] = 0;
    	//特殊情况 子串只有一个字符
    	if (subLen == 1)
    	{
    		return next;
    	}
    
    	next[2] = 1;
    	int start = 1;
    	int end = 2;
    	int count = 1;
    	for (size_t i = 3; i <subLen + 1; i++)
    	{
    		//i 当前字符的下标，计算它的next值
    		if (sub_str[start] == sub_str[end])
    		{
    			next[i] = ++count;
    			start++;
    			end++;
    
    		}
    		else
    		{
    			//遇到不相等，那就只能从头开始比较咯，
    			start = 1;
    			count = 1;
    			if (sub_str[start] == sub_str[end])
    			{
    				next[i] = ++count;
    				//相等前缀往后走
    				start++;
    			}
    			else
    			{
    				next[i] = 1;
    				//不相等 start停留在第一个位置
    			}
    			//后缀一直往后走
    			end++;
    
    		}
    	}
    	return next;
    }

# next 数组优化 #

后来前辈们发现KMP还是有缺陷的，比如我们的主串aaaabcde和子串aaaaax，按照KMP算法next值分别为012345，按照KMP算法比较如下：

![SouthEast 2][]

其中二、三、四、五是多余的判断，因为其位置上的字符都和首字符'a'相等，那么可以用首位next\[1\]的值进行取代当前next\[\]的值。下面请看代码，就加了2行语句。

/*
    获取子串的next数组
    优化后的next数组
    */
    int* NextKMP2(uchar* sub_str)
    {
    	int subLen = sub_str[0];
    	int* next = (int*)malloc(sizeof(int)*(subLen + 1));
    	next[1] = 0;
    	//特殊情况 子串只有一个字符
    	if (subLen == 1)
    	{
    		return next;
    	}
    
    	next[2] = 1;
    	int start = 1;
    	int end = 2;
    	int count = 1;
    	for (size_t i = 3; i <subLen +1; i++)
    	{
    		//i 当前字符的下标，计算它的next值
    		if (sub_str[start] == sub_str[end])
    		{
    			next[i] = ++count;
    			start++;
    			end++;
    			
    		}
    		else
    		{
    			//遇到不相等，那就只能从头开始比较咯，
    			start = 1;
    			count = 1;
    			if (sub_str[start] == sub_str[end])
    			{
    				next[i] = ++count;
    				//相等前缀往后走
    				start++;
    			}
    			else
    			{
    				next[i] = 1;
    				//不相等 start停留在第一个位置
    			}
    			//后缀一直往后走
    			end++;
    			
    		}
    		//优化 如果start指向的字符和当前字符相等，那么就取前缀相同字符的next值
    		if (sub_str[start] == sub_str[end])
    		{
    			next[i] = next[start];
    		}
    
    	}
    	return next;
    }

# 完整代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef unsigned char uchar;
    /*
    获取子串的next数组
    优化后的next数组
    */
    int* NextKMP2(uchar* sub_str)
    {
    	int subLen = sub_str[0];
    	int* next = (int*)malloc(sizeof(int)*(subLen + 1));
    	next[1] = 0;
    	//特殊情况 子串只有一个字符
    	if (subLen == 1)
    	{
    		return next;
    	}
    
    	next[2] = 1;
    	int start = 1;
    	int end = 2;
    	int count = 1;
    	for (size_t i = 3; i <subLen +1; i++)
    	{
    		//i 当前字符的下标，计算它的next值
    		if (sub_str[start] == sub_str[end])
    		{
    			next[i] = ++count;
    			start++;
    			end++;
    			
    		}
    		else
    		{
    			//遇到不相等，那就只能从头开始比较咯，
    			start = 1;
    			count = 1;
    			if (sub_str[start] == sub_str[end])
    			{
    				next[i] = ++count;
    				//相等前缀往后走
    				start++;
    			}
    			else
    			{
    				next[i] = 1;
    				//不相等 start停留在第一个位置
    			}
    			//后缀一直往后走
    			end++;
    			
    		}
    		//优化 如果start指向的字符和当前字符相等，那么就取前缀相同字符的next值
    		if (sub_str[start] == sub_str[end])
    		{
    			next[i] = next[start];
    		}
    
    	}
    	return next;
    }
    
    /*
    获取子串的next数组
    没有优化的的next数组
    */
    int* NextKMP1(uchar* sub_str)
    {
    	int subLen = sub_str[0];
    	int* next = (int*)malloc(sizeof(int)*(subLen + 1));
    	next[1] = 0;
    	//特殊情况 子串只有一个字符
    	if (subLen == 1)
    	{
    		return next;
    	}
    
    	next[2] = 1;
    	int start = 1;
    	int end = 2;
    	int count = 1;
    	for (size_t i = 3; i <subLen + 1; i++)
    	{
    		//i 当前字符的下标，计算它的next值
    		if (sub_str[start] == sub_str[end])
    		{
    			next[i] = ++count;
    			start++;
    			end++;
    
    		}
    		else
    		{
    			//遇到不相等，那就只能从头开始比较咯，
    			start = 1;
    			count = 1;
    			if (sub_str[start] == sub_str[end])
    			{
    				next[i] = ++count;
    				//相等前缀往后走
    				start++;
    			}
    			else
    			{
    				next[i] = 1;
    				//不相等 start停留在第一个位置
    			}
    			//后缀一直往后走
    			end++;
    
    		}
    	}
    	return next;
    }
    
    /*
    用KMP算法查询子串在主串中的位置
    dest_str:目标字符串
    sub_str:子串
    next:子串的next数组
    begin:开始查询的位置
    return 返回子串在主串中的index
    */
    int IndexKMP(uchar* dest_str,uchar* sub_str,int* next,int begin)
    {
    	int subLen = sub_str[0];
    	uchar* dest = dest_str + 1 + begin;
    	uchar* sub = sub_str + 1;
    	int count = 0;
    	//和暴风算法一样
    	while (*dest != 0)
    	{
    		count++;
    		//判断第一个字符是否相等，不相等 主串往后移
    		if (*dest != *sub)
    		{
    			dest++;
    			continue;
    		}
    		//碰到相等字符，记录比较起始位置
    		uchar* temp = dest;
    		//走到这里主串和子串第一个字符相等，继续往下进行比较
    		sub++;
    		dest++;
    		while (*sub !=0)
    		{	
    			count++;
    			//相等继续比较后面的字符
    			if (*dest == *sub)
    			{
    				dest++;
    				sub++;
    			}
    			else
    			{
    				//遇到不相等的字符 就回溯
    				//BF算法就是从头再来了，主串回溯到标记的下一位继续和子串的第一位开始进行比较
    				//dest = temp + 1;
    				//sub = sub_str + 1;
    				//KMP 算法，就是比较字符不等时，next[]有值，主串不进行回溯，把子串进行回溯！这是KMP的核心思想。
    				if (next[sub - sub_str] == 0)//next[]值为0主串比较下一位
    				{
    					dest = temp + 1;
    					sub = sub_str + 1;
    				}
    				else
    				{
    					//sub = sub_str + 1 + next[sub - (sub_str + 1) + 1] - 1;
    					sub = sub_str + next[sub - sub_str];//别写错了哟，这里是关键。
    				}
    				break;
    			}
    		}
    		//子串遍历完毕，说明子串在主串中匹配完毕
    		if (*sub == 0)
    		{
    			printf("KMP算法字符比较的次数:%d\n", count);
    			return dest - (dest_str + 1) - subLen;
    		}
    	}
    	printf("没有找到\n");
    	return -1;
    }
    /*
    将普通字符串转换为KMP需要的字符串格式
    char* src = "abc";--> char* dest = {3,'a','b','c','\0'};
    */
    uchar* StrConvert(char* src)
    {
    	int len = strlen(src);
    	if (NULL == src || len == 0 )
    	{
    		return NULL;
    	}
    	int newLen = len + 2;//\0 占一个位置，字符数量占一个位置
    	uchar* str = malloc(sizeof(char)*newLen);
    	memset(str, 0, newLen);
    	str[0] = len;//为了是主串可以更长使用unsigned char ，所以主串最长不要超过255个字符
    	strncpy(str + 1, src, len);
    	return str;
    }
    /*
    用BF算法查询子串在主串中的位置
    dest:目标字符串
    sub:查询子串
    begin:开始查找的下标
    return 返回子串在主串中的index
    */
    int StrIndexBF(char* dest_str, char* sub_str, int begin)
    {
    	if (begin < 0)
    	{
    		begin = 0;
    	}
    	char* dest = dest_str + begin;
    	char* sub = sub_str;
    	int count = 0;//记录比较次数
    	//通过字符一个一个进行比较
    	while (*dest != 0)
    	{
    		count++;
    		//和子串第一个字符不相等
    		if (*dest != *sub)
    		{
    			dest++;
    			continue;
    		}
    		char* temp = dest;
    		//走到这里主串和子串第一个字符相等，继续往下进行比较
    		sub++;
    		dest++;
    		//遇到不相等的字符就回溯，主串回溯到标记的下一位继续和子串的第一位开始进行比较
    		while (*sub != 0)
    		{
    			count++;
    			if (*sub == *dest)
    			{
    				sub++;
    				dest++;
    			}
    			else
    			{
    				sub = sub_str;
    				dest = temp + 1;
    				break;
    			}
    		}
    		//判断子串是否遍历完毕,返回位置
    		if (*sub == 0)
    		{
    			printf("BF算法字符比较的次数:%d\n", count);
    			return dest - dest_str - strlen(sub_str);
    		}
    	}
    	printf("没有找到\n");
    	return -1;
    }
    
    /*
    打印next数组的数据
    */
    PrintNext(int* arr,int length)
    {
    	//next[0]为空闲空间
    	for (size_t i = 1; i < length; i++)
    	{
    		printf("%d  ", arr[i]);
    	}
    	printf("\n");
    	return 0;
    }
    
    /*
    KMP算法查找子串
    dest 目标字符串
    sub 查询子串
    begin 开始查找的下标
    */
    int StrIndexKMP(char* dest,char* sub,int begin)
    {
    	if (NULL == dest || NULL == sub || begin < 0)
    	{
    		printf("传入参数有误...\n");
    		return -1;
    	}
    	uchar* dest_ = StrConvert(dest);
    	uchar* sub_ = StrConvert(sub);
    	int* nextArr1 = NextKMP1(sub_);
    	int* nextArr2 = NextKMP2(sub_);
    	printf("KMP的 next   :");
    	PrintNext(nextArr1, sub_[0]+1);
    	printf("KMP的 nextval:");
    	PrintNext(nextArr2, sub_[0] + 1);
    	return IndexKMP(dest_,sub_, nextArr2,begin);
    }
    
    int main(int argc, char *argv[])
    {
    	char dest[256] = { 0 }, sub[256] = { 0 }, num[5] = { 0 };
    	int begin = 0;
    	while (1)
    	{
    		memset(dest, 0, 256);
    		memset(sub, 0, 256);
    		memset(num, 0, 5);
    
    		printf("请输入目标字符串(#退出):");
    		fgets(dest, 256, stdin);
    		dest[strlen(dest) - 1] = 0;//去掉换行符
    		if (strcmp(dest, "#") == 0)
    		{
    			break;
    		}
    
    		printf("请输入查询起始位置(不输入从0开始):");
    		fgets(num, 5, stdin);
    		if (strlen(num) != 1)
    		{
    			num[strlen(num) - 1] = 0;//去掉换行符
    			sscanf(num, "%d", &begin);
    		}
    
    
    		printf("请输入查询子串:");
    		fgets(sub, 256, stdin);
    		sub[strlen(sub) - 1] = 0;//去掉换行符
    
    		int index = StrIndexBF(dest, sub, begin);
    		printf("BF:dest=%s,sub=%s,begin=%d,index=%d\n", dest, sub, begin, index);
    		index = StrIndexKMP(dest, sub, begin);
    		printf("KMP:dest=%s,sub=%s,begin=%d,index=%d\n", dest, sub, begin, index);
    	}
    	return 0;
    }

# 运行结果检测 #

我们主要看next数组值和优化后的nextval数组值是否推导正确，这是KMP算法的关键，如果你能写BF算法然后能将next数组用代码推算出来，那么你的KMP算法就ok了，然后可能就是一些细节的上的完善了。

![SouthEast 3][]

[BF]: http://blog.csdn.net/qq_29542611/article/details/79189529
[SouthEast]: /images/20220531/50a4aba1e8aa4812a4033e0f433905d8.png
[SouthEast 1]: /images/20220531/5a93731db62f439cb041bc2bc5218ffd.png
[SouthEast 2]: /images/20220531/91b5a33ac10c464faf275058a4a5ca74.png
[SouthEast 3]: /images/20220531/ca0d1e149e80463196c0f822b4d80593.png