kmp.cpp

串的KMP算法

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <string.h>

void Get_next(char *p,int next[]){
	int i,j,len;
	len=strlen(p);	i=0;
	next[0]=-1;	j=-1;
	while(i<len){
		if(j==-1 || p[i]==p[j]){
			++i;	
			++j;
			next[i]=j;
		}
		else
			j=next[j];
	}
}

int Index_KMP(char *s,char *p,int pos,int next[]){
	int i,j,slen,plen;
	i=pos;
	j=0;
	slen=strlen(s);
	plen=strlen(p);
	while(i<slen && j<plen){
		if(j==0 || s[i]==p[j]){
			++i;	++j;
		}
		else
			j=next[j];
	}
	if(j>=plen)
		return i-plen-pos;
	else
		return -1;
}

void main(){
	int next[9];
	int i;
	char s[19]="abcdabaabcacafcd";
	char p[9]="abaabcac";
	int pos=0;
	Get_next(p,next);
	for(i=0; i<(int)strlen(p) ;i++)
		printf("%d ",next[i]);
	printf("\n");
	pos=Index_KMP(s,p,pos,next);
	cout<<pos<<endl; 
}