朴素模式匹配算法和KMP匹配算法 详细

朴素模式匹配算法和KMP匹配算法

一、朴素模式

假设我们要从主串S=”goodgoogle"中找到子串T=“google"的位置，步骤如下：

i表示主串的当前位置下标，j表示子串的当前位置下标，如上图在第一轮比较（i=1开始）中j=4和i=4的位置不匹配，接下来就要指针回退，从i=2开始比较，如下：

如此反复直到比较到 i =（主串长度-子串长度+1）的位置或者 j = 子串的长度 就退出比较循环，上面的主串和子串在比较到i=5的位置就完全匹配了。

#include <stdio.h>
 
int Index(const char S[], const char T[], int pos){
	int i = pos; //主串当前下标
	int j = 1;	 //子串当前下标
	//S[0]是主串的长度，T[0]是子串的长度
	while(i <= S[0] && j <= T[0]){
		//如果相等则继续向下比较
		if(S[i] == T[j]) {
			++i;
			++j;
		//如果不等则指针回退
		}else{
			i = i - j + 2; //主串回退
			j = 1;
		}
	}
	//j>T[0]则说明子串被完全匹配
	if( j > T[0]) return i - T[0];
	else return 0;
}
 
int main(){
	char S[] = {10, 'g', 'o', 'o', 'd', 'g', 'o', 'o',
		'g', 'l', 'e'};	
	char T[] = {6, 'g', 'o', 'o', 'g', 'l', 'e'};
	int i =	Index(S, T, 1);
	printf("%d\n", i);
 
	return 0;
}

分析一下这种匹配算法最好的情况时间复杂度是O(1)只需要一次比较，最坏的情况是每次最后一个字符不匹配，时间复杂度是O(m*n) m是主串长度n是子串的长度。

朴素模式匹配算法时间复杂度分析如下：（n为主串长度，m为模式串长度）

时间复杂度:

最好情况
O(1) 一开始就匹配成功。

最坏情况
O((n-m+1)*m) 每次不成功的匹配都发生在模式串的最后一个字符。

平均情况
O(n+m) 根据等概率原则，平均是(n+m)/2次查找。

二、KMP算法

像二进制这样的多个0和1重复的字符串，上面的模式匹配需要挨个遍历是非常慢的，KMP算法可以大大避免重复遍历的情况。

下面我们来看看KMP算法的基本原理

如上，可以看到主串S和子串T在第一轮比较的时候，前面5个相等，只有i=6和j=6的位置不等。由于子串T中abcde这5个字符本身互不相等，可以知道子串T中a就不可能和j=2、3、4、5的位置的字符相等。所以可以直接跳到i=6的位置进行比较。

再看上图，如果子串T中存在重复的元素（比如j=1,2和j=4,5处的字符），按照上面的分析，我们可以直接跳到i=4的位置比较，但是我们已经知道j=1,2和j=4,5相等，并且i=4,5和j=4,5相等，所以可以不用比较i=4,5和j=1,2。

KMP模式匹配算法就是为了不让i指针回退，既然i值不回退，我们就要考虑变化j的值了。通过上面的观察可以发现，j值的变化与主串其实没有什么关系，而是取决于子串T中是否有重复问题。

我们把T串各个位置的j值的变化定义为一个数组next,那么next的长度就是T串的长度，可以得到下面函数：

#include <stdio.h>
 
void get_next(const char T[], int *next){
	
	int i,j;
	i = 1;
	j = 0;
	next[1] = 0;
	//T[0]是子串T的长度
	while(i < T[0]){
		//T[i]表示后缀的单个字符
		//T[j]表示前缀的单个字符
		if( j==0 || T[i] == T[j]){
			++i;
			++j;
			next[i] = j;
		}else{
			j = next[j];
		}
	}
}
 
int Index_KMP(const char S[], const char T[], int pos){
	int i = pos;
	int j = 1;
	int next[255];
	get_next(T, next);
 
	while(i <= S[0] && j <= T[0]){
		//相对于朴素算法，增加了一个j==0的判断
		if( j==0 || S[i] == T[j]){
			++i;
			++j;
		}else{
			//j回退到合适的位置，i的值不变
			j = next[j];
		}
	}
	if( j>T[0]){
		return i-T[0];
	}else{
		return 0;
	}
}
int main(){
 
	return 0;
}

整个算法的时间复杂度为O（n+m）