kmp.cpp

来自「数值分析中常用的几种算法的实现」· C++ 代码 · 共 34 行

#include<string.h>
int f[200];
void swap(char *s1,char *s2){
	char temp[110];
	strcpy(temp,s1);
	strcpy(s1,s2);
	strcpy(s2,temp);
	return;
}
int kmp(char p[],char tag[],int len){
	int posp=0,post=0;
	int lengthp=len,lengtht=strlen(tag);
	while(posp<lengthp&&post<lengtht){
		if(p[posp]==tag[post]){
			posp++;
			post++;
		}
		else if(posp==0) post++;
		else posp=f[posp-1]+1;
	}
	if(posp<lengthp) return -1;
		else return post-lengthp;
}
void fail(char p[],int len){
	int lengthp=len;
	f[0]=-1;
	for(int j=1;j<lengthp;j++){
		int 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;
	}

}