next数组与KMP算法

本文主要是介绍next数组与KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

KMP算法详解请参考：next数组实现及KMP算法（点这里），感谢大佬的文章！！！

反复研究，终于开窍搞出了代码！

next数组的实现：

//实现next数组 
int get_next(char T[],int next[]){
	next[0]=-1;
	int i=0,j=-1;
	int len=strlen(T);
	while(i<len){
		if(j==-1||T[i]==T[j]){
			i++;
			j++;
			next[i]=j;
		}
		else{
			j=next[j];
		}
	}
}

KMP查找：

//KMP算法
#include <iostream> 
#include <cstring>
#define SIZE 100
using namespace std;
int getNext(char T[],int next[]){
	next[0]=-1;
	int i=0,j=-1;
	int len=strlen(T);
	while(i<len){
		if(j==-1||T[i]==T[j]){
			i++;
			j++;
			next[i]=j;
		}
		else{
			j=next[j];
		}
	}
}
int KMP(char S[],char T[],int next[]) {
	int i=0,j=0;
	int S_len=strlen(S);
	int T_len=strlen(T);
	while(i<S_len&&j<T_len){
		if(j==-1||S[i]==T[j]){
			i++;
			j++;
		}
		else{
			j=next[j];
		}
	}
	if(j==T_len)
		return i-j;
	else
		return -1;
}
int main(){
	char S[SIZE];
	char T[SIZE];
	int next[SIZE];
	cout<<"请输入主串：";
	cin>>S;
	cout<<"请输入模式串：";
	cin>>T;
	getNext(T,next);
	int a=KMP(S,T,next);
	if(a==-1)
		cout<<"匹配失败！" ;
	else
		cout<<"匹配成功！起始下标为"<<a; 
}

这篇关于next数组与KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！