kmp.cpp

《数据结构-使用C语言》第三版

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

#define MaxSize 100

#include"String.h"

int main()
{
	int i,t;
	String S, T;
	int next[MaxSize];
	void GetNext(String T, int next[]);
	int KMP(String S,int start, String T, int next[]);
	
	while(scanf("%s%s",S.str,T.str)!=EOF)
	{
		S.length=strlen(S.str);
		T.length=strlen(T.str);
		GetNext(S, next);
		
		for(i=0;i<S.length;i++)
		printf("%d ",next[i]);
		printf("\n");
		
		t=KMP(S, 0, T, next);
		if(t<0)printf("NO\n");
		else printf("%d\n",t);
	}
	return 0;
}

void GetNext(String T, int next[])
{
	int j=1,k=0;
	next[0]=-1;
	next[1]=0;
	while(j<T.length)
	{
		if(T.str[j]==T.str[k])
		{
			next[j+1]=k+1;
			j++;
			k++;
		}
		else if(k==0)
		{
			next[j+1]=0;
			j++;
		}
		else k=next[k];
	}
}

int KMP(String S, int start, String T, int next[])
{
	int i=start, j=0, v;
	while(i<S.length && j<T.length)
	{
		if(S.str[i]==T.str[j])
		{
			i++;
			j++;
		}
		else if(j==0)i++;
		else j=next[j];
	}
	if(j==T.length)v=i-T.length;
	else v=-1;
	return v;
}