KMP算法

关于c语言版数据结构书上的代码，我整理了一下，具体思路和书上拟合。

注意我这里存字符的时候从1开始存的，省的考虑位置问题。

1.首先得到模式串 t 的next值。

当模式串与主串失配时，我们不再回溯主串指针i，而让模式串向右划，那么滑到哪个位置呢？我们假设他划到k位置，即此时主串指针 i 应与模式串的第k个字符继续比较（k<j）。根据这点，我们给出next数组的定义。（关于匹配原理这里我不在讲怎么推了，我就讲怎么用编程实现。这有两篇博客可以看看，挺清楚的http://www.cnblogs.com/c-cloud/p/3224788.htmlhttp://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html）

next数组的定义如下：

我们首先规定next [ 1 ] = 0（这里的j就是代表next [ i ]）.然后每当j = 0 或者 t.ch[ i ] = t.ch [ j ]时，就i++,j++,next[ i ] = j;看个例子理解一下。

假设有模式串aabb，要求他的next值过程如下：

1.当i = 1时,规定 j = 0(这里的 j 其实就是next[ i ]数组)。满足条件j = 0,故i++,j++,next[ i ] = j;

此时i = 2，j = 1。这就求得i = 2 时的next值啦！

2.当i = 2时，满足t.ch[ i ] = t.ch [ j ]，故i++,j++,next[ i ] = j;

此时i = 3，j = 2。这就求得i = 3时的next值啦。

3.当i = 3时，不满足t.ch[ i ] = t.ch [ j ]或 j = 0,故 j = next[ j ] = 1;

继续判断 ，它还是不满足t.ch[ i ] = t.ch [ j ]或j = 0，故j = next[ j ] = 0;

继续判断，它满足 j = 0,故，i++,j++,next[ i ] = j;

此时i = 4, j = 1。（通过这个我们可以看出j = next[ j ]的作用，它就是判断t.ch[ i ] 是否等于 t.ch [ j ]的，如果不相等，就把j向前回溯直到找到一个next[ j ]使他们相等或者j = 0为止）

通过这种方式我们就得到了模式串aabb的next数组值。

代码如下： 

void get_next(SString t){
	int i = 1;
	int j = 0;
	next[1] = 0;
	while(i<t.length){
		if(j==0 || t.ch[i]==t.ch[j]){
			i++;
			j++;
			next[i]=j;
		}
		else
			j = next[j];
	}
}

2.进入KMP算法。

KMP算法和BF算法极为相似，区别是当匹配过程产生“失配”时，指针 i 不变，让指针 j 退回到next[ j ] 所指示的位置上重新进行比较，并且当指针 j 退至0时，指针 i 和指针 j 需同时加1。即若主串的第 i 个字符和模式串的第 1 个字符不等，应从主串的第 i + 1个字符起重新比较。

int Index_KMP(SString s,SString t,int pos){
	int i = pos;
	int j = 1;
	while(i<=s.length && j<=t.length){
		if(j==0 || s.ch[i]==t.ch[j]){
			i++;
			j++;
		}
		else
			j = next[j];
	}
	if(j>t.length)
		return i-t.length;
	else
		return 0;
}

完整代码为：

#include<bits/stdc++.h>
#pragma execution_character_set("utf-8")
const int maxn = 1000;
using namespace std;
int next[maxn]; 
typedef struct{
	int length;
	char ch[maxn];
}SString;
 
void get_next(SString t){
	int i = 1;
	int j = 0;
	next[1] = 0;
	while(i<t.length){
		if(j==0 || t.ch[i]==t.ch[j]){
			i++;
			j++;
			next[i]=j;
		}
		else
			j = next[j];
	}
}
 
int Index_KMP(SString s,SString t,int pos){
	int i = pos;
	int j = 1;
	while(i<=s.length && j<=t.length){
		if(j==0 || s.ch[i]==t.ch[j]){
			i++;
			j++;
		}
		else
			j = next[j];
	}
	if(j>t.length)
		return i-t.length;
	else
		return 0;
}
 
int main(){
	int pos;
	int status;
	SString s,t;
	cout<<"请输入主串长度：";
	cin>>s.length;
	cout<<"请输入主串字符：";
	int c = getchar();
	scanf("%s",s.ch+1);
	cout<<"请输入模式串长度：";
	cin>>t.length;
	cout<<"请输入模式串字符：";
	c = getchar();
	scanf("%s",t.ch+1);
	cout<<"请输入你要查找的首位置：";
	cin>>pos;
	get_next(t);
	status = Index_KMP(s,t,pos); 
	if(status)
		cout<<"匹配成功，模式串在主串中第一次出现的位置为："<<status<<endl;
	else
		cout<<"匹配失败！"<<endl;
	return 0;
}

 3.KMP算法的优化

其实上述算法还有缺陷，例如模式串“aaaab”在和主串“aaabaaaab”匹配时,当i=4，j=4时，s.ch[4]！=t.ch[4]，由next[ j ] 的指示还需要进行i =4、j=3，i=4、j=2，i=4、j=1这3此比较。实际上，因为模式串中第1～3个字符和第四个字符都相等，因此不需要再和主串中第4个字符相比较，而可以将模式串连续向右滑动4个字符的位置直接进行i=5、j=1时的字符比较。这就是说，若按上述定义得到next[ j ] = k，而模式串中t_ j = t_k，则当主串中字符s_i和t_ j比较不等时，无需再和t_k进行比较，而直接和t_next[ k ]进行比较，换句话说，此时的next[ j ] 应和next[ k ] 相同。由此可计算next函数修正值的算法。

以下是模式串“aaaab”的 next修正值（nextval）模拟过程：

得到nextval 的算法如下：

void get_nextval(sstring t){
	int i=1;
	int j=0;
	nextval[1]=0;
	while(i<t.length){
		if(j==0 || t.ch[i]==t.ch[j]){
			i++;
			j++;
			if(t.ch[i]!=t.ch[j])
				nextval[i]=j;
			else
				nextval[i]=nextval[j];
		}
		else
			j=nextval[j];
	}
}

经过优化的KMP算法完整代码如下：

#include<bits/stdc++.h>
const int maxn = 1000;
using namespace std;
int next[maxn];
int nextval[maxn];
typedef struct{
	int length;
	char ch[maxn];
}sstring;
void get_next(sstring t){
	int i=1;
	int j=0;
	next[1]=0;
	while(i<t.length){
		if(j==0 || t.ch[i]==t.ch[j]){
			i++;
			j++;
			next[i]=j;
		}
		else
			j=next[j];
	}
}

void get_nextval(sstring t){
	int i=1;
	int j=0;
	nextval[1]=0;
	while(i<t.length){
		if(j==0 || t.ch[i]==t.ch[j]){
			i++;
			j++;
			if(t.ch[i]!=t.ch[j])
				nextval[i]=j;
			else
				nextval[i]=nextval[j];
		}
		else
			j=nextval[j];
	}
}

int KMP(sstring s,sstring t,int pos){
	int i=pos;
	int j=1;
	while(i<=s.length && j<=t.length){
		if(j==0 || s.ch[i]==t.ch[j]){
			i++;
			j++;
		}
		else
			j=nextval[j];
	}
	if(j>t.length)
		return i-t.length;
	else
		return 0;
}

int main(){
	sstring s,t;
	int pos;
	int status;
	cout<<"请输入主串长度：";
	cin>>s.length;
	cout<<"请输入主串字符：";
	scanf("%s",s.ch+1);
	cout<<"请输入模式串长度：";
	cin>>t.length;
	cout<<"请输入模式串字符：";
	scanf("%s",t.ch+1);
	cout<<"请输入你要查询的首位置：";
	cin>>pos;
	get_next(t);
	cout<<"我们的得到的模式串next数组值为：";
	for(int i=1;i<=t.length;i++)
		cout<<next[i]<<" ";
	cout<<endl;
	get_nextval(t);
	cout<<"我们得到的模式串next数组的修正值nextval数组值为：";
	for(int i=1;i<=t.length;i++)
		cout<<nextval[i]<<" ";
	cout<<endl<<"KMP算法结果为：";
	status = KMP(s,t,pos);
	if(status)
		cout<<"匹配成功，模式串在主串中第一次出现的位置为："<<status<<endl;
	else
		cout<<"匹配失败！"<<endl;
	return 0;
}