【算法篇】KMP算法，一种高效的字符串匹配算法

我们今天了解一个字符串匹配算法-KMP算法，内容难度相对来说较高，建议先收藏再细品！！！

KMP算法的基本概念

KMP算法是一种高效的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。

该算法的主要使用场景就是在字符串（也叫主串）中的模式串（也叫字串）定位问题，常见的有“求子串出现的起始位置”、“求子串的出现次数”等。

解决什么问题

假设有两个字符串,分别为文本串和模式串，如下：

求在文本串中是否出现过上面的模式串。

暴力解法

当出现不匹配的字符时，暴力算法会进行如下两个操作：

向后移动模式串
目标串和模式串的指针都回溯

KMP优化解法

使用暴力算法的时间复杂度较高，如何去优化呢？

优化方向：防止或减少主串指针回溯

当出现不匹配的字符时，目标串指针不动，只移动模式串。

移动前，指针左边的字符已经匹配了，所以要让移动后的目标串的指针不会苏，需要保证：模式串移动之后，在指针左边的字符也是匹配的。

找相同字符必须是从模式串第一个位置开始
模式串移动方式由能找到的最长的相同字符决定，如果不是最长的，可能会漏掉能匹配的内容。
找到的最长的相同字符串长度必须小于已经匹配的内容长度，前后部分可以有交叉内容

KMP算法小结

发生不匹配时，指针所指的下标等于已经匹配的长度
发生不匹配时，需要移动的长度 = 已经匹配的长度 - 前后相同的最大长度
前后相同的最大长度为空的地方用-1补齐

KMP算法中的next数组

当目前的C和A不匹配时，由于A的前面也全都是A，所以前面也一定不匹配，对于这个模式串，可以直接将指针移动到-1的位置。

所以需要再对next数组进行改进，改进后的数组我们命名为nextval。

优化next数组

总结：若str[j] == str[next[j]]，那么nextval[j] = nextval[next]，否则nextval[j] = next[j]

判断是否匹配

先给定两个字符串，分别表示文本串和模式串，通过kmp(稍后写这个函数)进行比较，找到第一次出现模式串的位置，如果没有匹配上则给出提示。

char *text = "aaaaaabaaa",*pattern = "aaaab";
int index = kmp(text,pattern);
if(index == -1)
{
	cout << "没有匹配上内容";
} 
else{
 	cout << "匹配上了，起始位置为:" << index;
}

输出next数组

next指针用来动态获取模式串的长度

int kmp(char *text,char *pattern){
	int index = -1;
	int txt_len = strlen(text),ptn_len = strlen(pattern);
	int *next = (int *)malloc(sizeof(int) * ptn_len);
	get_next(pattern,next,ptn_len);

	free(next);
	return index;
}

计算next数组

若str[j] == str[k]时，next[j+1] = k+1
若str[j] != str[k]时，k = next[k]

void get_next(char *str,int *next,int len){
	int j = 0,k = -1;
	next[0] = -1;
	while(j < len-1){
		if(k == -1 || str[j] == str[k]){
			k++;
			j++;
			next[j] = k;
		}
		else k = next[k];
	} 
}

遍历输出next数组

从下标为0的位置到ptn_len依次输出next数组内的元素

int kmp(char *text,char *pattern)
{
	int index = -1;
	int txt_len = strlen(text),ptn_len = strlen(pattern);
	int *next = (int *)malloc(sizeof(int) * ptn_len);
	get_next(pattern,next,ptn_len);
	
	for(int i=0;i<ptn_len;i++){
		printf("%d ",next[i]);
	}
	
	free(next);
	return index;
}

输出nextval数组

将next数组变为nextval数组（此处的next数组实际上是nextval数组）

if(k == -1 || str[j] == str[k]){
	k++;
	j++;
	if(str[j] == str[k]){
		next[j] = next[k];
	}
	else{
		next[j] = k;
	}
}
else{
	k = next[k];
}

输出匹配位置

int index = -1,txt_idx = 0,ptn_idx = 0;
... ...
get_next(pattern,next,ptn_len);

while((txt_idx < txt_len) && (ptn_idx < ptn_len))
{
	if(text[txt_idx] == pattern[ptn_idx] || ptn_idx == -1){
		txt_idx++;
		ptn_idx++;
	}
	else{
		ptn_idx = next[ptn_idx];
	}
}

if(ptn_idx >= ptn_len){
	index = txt_idx - ptn_len;
}