kmp_suanfa.cpp

KMP模式匹配算法,实现了用KMP算法无回溯查找字符串的功能

#include<iostream>
using namespace std;
int Stringlength(char* s);

int* failedfuction(char* P){
	int Plength=0;
	int j=0;
	int i=0;
	Plength=Stringlength(P);
	int* F=new int[Plength];
	F[0]=-1;
	for(j=1;j<Plength;j++){
	i=F[j-1];
	while((P[j]!=P[i+1])&&i>=0) i=F[i];
	if(P[j]==P[i+1]) F[j]=i+1;
	else F[j]=-1;
	}
return F;
}

int kmp(char* P,char* T){
	int Plength=0;
	int Tlength=0;
	int posP=0;
	int posT=0;
	int* F=NULL;
	F=failedfuction(P);
	Plength=Stringlength(P);
	Tlength=Stringlength(T);
	while((posP<Plength)&&(posT<Tlength)){
		if(P[posP]==T[posT]){
		posP++;
		posT++;
		}
		else{
			if(posP==0)
				posT++;
			else
				posP=F[posP-1]+1;
		}
	
	}

	if(posP==Plength)
		return posT-Plength;
	else 
		return -1;
}

int Stringlength(char* s){
	int i=0,j=0;
	while(s[i++]!=0)
		j++;
	return j;
}

int main(){
char* smain="litiantiantiantianyuyu";
char* spat="tiany";
int location=0;

location=kmp(spat,smain);
cout<<location;
return 0;

}