KMP算法解析

 

一.理论基础

1.什么是kmp算法

同BF算法一样，就是串的模式匹配算法。

前面已经学过，我想都应该明白BF算法，就是用一种最直观的方式进行模式匹配。

优点：非常容易理解，是我们常用的思维方式来编程；

缺点：效率比较低，在匹配不成功的时候，回朔做了许多无用功；

 

从而根据其缺点，KMP算法就在回朔的时候做了工作，减少其无用功，那么怎么去减少回朔的工作呢？

下面举例说明：

例如：

s = abababc

t = ababc

其匹配过程如下图：

从图中我们看到了具体的变换过程，就是在回朔的过程中做了许多工作，S的i不需要回朔到1，只需要T回朔就可以了，那么怎么知道T回朔到什么位置才好呢？而从上面的图中我们也会发现，其实回朔跟S串是没有关系的，i压根就没变，变的是T的j，故而需要回朔的是T--待匹配模式串，所有回朔的位置是由T串的特点决定的！！当然，就这是问题2，求next数组。

 

2.为什么要求next数组

什么是next数组，简而言之，就是当不匹配的时候，从当前j的位置需要回朔的位置k

如上面的图中，当j=4的时候，回朔的位置是2，故而next[4]=2,这就是next的价值所在：决定在位置j不匹配的时候，回退到位置next[j].

 

3.next如何求之理论基础

既然求next完全是T的事，那么我这里就不像那些书上那样从S去分析，直接切入正题从T分析！书上有时候说的反而有碍思维，要是完全照书，我就不写这些了！

首先实例分析：

 2。代码

 

#include <iostream>
using namespace std;

int strLen(const char *s){
	if(!s) throw "串不能为空！\n";
	int i=0;
	while(*s != '\0'){
		i++;
		s++;
	}
	return i;
}		

/**
	*求next数组值
	*求模式t的next值并存入next数组中
	*t :待求模式数组
	*n :模式数组长度
	*next：next数组
	*/
void getNext(const char* t, int n, int* next){
	int i=0, j=-1;
	next[0] = -1;
	while(i < n){
		//如果j==-1，则回退到了开始位置(只有当开始的时候j才为-1，only one,以后至少都是0)
		//如果相等，匹配，故而向前，此时i的next的值就是j，且存的是最大的j
		if(j == -1 || t[j] == t[i]){
			i++;
			j++;
			next[i]=j;
		}else{//如果不等或j为其他,则j回到next[j]位置继续匹配
			j = next[j];
		}
	}
}

//1.Brute-Force算法(BF算法)
//子串定位（p若属于s，返回串p在s中的位置，否则返回0）
int strIndex(const char* s, const char* p){
	if(!s || !p) throw "串不能为空！\n";
	int i=0, j=0, r = 1;
	int sl = strLen(s);
	int pl = strLen(p);
	if(sl < pl) throw "参数异常，串长度！\n";
	while(i<sl && j<pl){
		if(s[i] == p[j]){
			i++; j++;
		}else{//恢复开始的位置的下一个位置
			i = i-j+1;
			j = 0;
		}
	}
	if(j >= pl) r = i-pl+1;
	else r = -1;
	return r;
}		


//2.KMP算法
//具体的讲解，见博文
int strIndex_kmp(const char* s, const char* p){
	if(!s || !p) throw "串不能为空！\n";
	int i=0, j=0, r = 1;
	int sl = strLen(s);
	int pl = strLen(p);
	if(sl < pl) throw "参数异常，串长度！\n";
		
	//求next
	int *next = new int[pl];
	getNext(p, pl, next);
	cout<<"next数组:";
	for(int j=0; j<pl; j++){
			cout<<next[j]<<" ";	
	}	
	cout<<endl;
	
	while(i<sl && j<pl){
		if(j==-1 || s[i] == p[j]){
			i++; j++;
		}else{//恢复到next[j]
			j = next[j];
		}
	}
	if(j >= pl) r = i-pl+1;
	else r = -1;
	delete next;
	return r;
}

int main(){
	//char a[] = {'a','c','a','b','a','a','b','a','a','b','c','a','c','a','a','b','c','\0'};
	//char b[] = {'a','b','a','a','b','c','\0'};
	char a[] = {'a','b','a','b','a','b','c','\0'};
	char b[] = {'a','b','a','b','c','\0'};
	try{
		cout<<"BF算法："<<strIndex(a ,b)<<endl;
		cout<<"KMP算法："<<strIndex_kmp(a, b)<<endl;

	}catch(const char* s){	
		cout<<s<<endl;
	}
}