KMP算法

xiaoxiaodaining 2020-03-22 原文

KMP 算法

看了好多没搞懂，然后看了海大的知乎一下子清晰了好多附海大链接

首先先理解一下PMT表：

现在有一个字符串”ababababca”和一个用来匹配的子串“abababca”

对子串进行分割：

分为”a”,”ab”,”aba”,”abab”,”ababa”,”ababab” ,”abababc”,”abababca”

分别对这些分割的字串找到他们的前缀和后缀例如“aba” 的前缀有”a”,”a,b”后缀有’a’,’ba’,’ba’

前缀和后缀抑制的情况只有‘a’所以可以跳跃的最大距离就为1.我们根据这个子串来画出PMT表

char	a	b	a	b	a	b	c	a
index	0	1	2	3	4	5	6	7
value	0	0	1	2	3	4	0	1

下面我们先用代码来实现一下具体在代码求出PMT表的value值。

#include <stdio.h> 
#define MAXN 100 
#include <string.h>
int main() {
	char str1[]= "abababca"; 

	
	int next[MAXN];

	int i = 0, j = -1 ;  //使用-1为了好判断第一个
	while (i < strlen(str1)) {
		
		if ( j== -1 ||str1[i] == str1[j]) {
			
			next[i] = j; 
			++i; 
			++j; 
			printf("%d\n", i); 
			 
		}
		else {
			j = next[j];
		}
		
	}
	for (int i = 0; i < 8; ++i) {
		++next[i]; 
	}
	for (int i = 0; i < 8; ++i) {
		printf("%d ", next[i]); 
	}
	return 0; 
}

求出了PMT表后，我们就可以根据PMT表来优化字符串匹配

主串：ababababca

字串：abababca

在c的位置出现了匹配失败也就是意味着在前六个字符匹配都是成功的，此时来看一下PMT表也就是第5个数那边（从0开始索引）value值为4。这意味着在C前4个字符与字串的前4个字符完全一致。此时我们进行匹配完全可以从子串的第五个字符开始。

来完整实现一下kmp匹配

int kmp(char* s1, char* s2) {
	int i = 0;
	int j = 0; 
	while (i < strlen(s1) || j < strlen(s2)) {
		if (j == -1 || s1[i] == s2[j]) {
			i++; 
			j++; 
		}
		else {
			j = next[j - 1]; 
		}
	}
	if (j == strlen(s2)) {
		return i - j; 
	}
	return -1; 
}

完整代码：

#include <stdio.h> 
#define MAXN 100 
#include <string.h>

int next[MAXN];
int kmp(char* s1, char* s2) {
	int i = 0;
	int j = 0; 
	while (i < strlen(s1) || j < strlen(s2)) {
		if (j == -1 || s1[i] == s2[j]) {
			i++; 
			j++; 
		}
		else {
			j = next[j - 1]; 
		}
	}
	if (j == strlen(s2)) {
		return i - j; 
	}
	return -1; 
}

int main() {
	char str1[]= "abababca"; 
	char str2[] = "ababababca"; 

	


	int i = 0, j = -1 ;  //使用-1为了好判断第一个
	while (i < strlen(str1)) {
		
		if ( j== -1 ||str1[i] == str1[j]) {
			
			next[i] = j; 
			++i; 
			++j; 
			printf("%d\n", i); 
			 
		}
		else {
			j = next[j];
		}
		
	}
	for (int i = 0; i < 8; ++i) {
		++next[i]; 
	}
	//for (int i = 0; i < 8; ++i) {
	//	printf("%d ", next[i]); 
	//}
	int result = kmp(str2, str1);
	if (result == -1) {
		printf("不存在");
	}
	else {
		printf("在第%d位置存在", result); 
	}
	return 0; 
}