test2.cpp

数据结构中相关ADT的C++实现,注解清晰,让你快速掌握

//模式匹配的改进算法
#include<iostream.h>
#include<string.h>
typedef struct
{
	char * ch;
	int * next;//用于存放一个长度为length的数组,
	           //next[j-1]代表模式串中第j个位置与主串不匹配时,在模式中需重新和主串中该字符进行比较的字符的位置
	int length;
}sstring;
void assign(sstring & t,char * chars)
{
//生成一个其值等于串常量chars的串T

	int i;
i=strlen(chars);
	if(!i)
	{
		t.ch=NULL;t.length=0;
	}
	else
	{
		t.ch=new char[i];
		t.length=i;
		for(i=0;i<t.length;i++)
			t.ch[i]=chars[i];
	}
}
void get_next(sstring & t)
{
	//求模式串的next函数值并存入数组next.
	t.next=new int[t.length+1];
	int j=1;
	t.next[0]=0;
	t.next[1]=0;
	int k=0;
	while(j<=t.length)
	{
		if(k==0||t.ch[j-1]==t.ch[k-1])
		{
			++k;++j;
			if(t.ch[j-1]!=t.ch[k-1])
				t.next[j]=k;
			else
				t.next[j]=t.next[k];
		}
		else
		k=t.next[k];
	}
}
int index_kmp(sstring s,sstring t,int pos)
{
	//利用模式串t的next函数求t在主串s中第pos个字符之后的位置的KMP算法.
	//其中,t非空,1<=pos<=s.length
	get_next(t);
	int i=pos,j=1;
	while(i<=s.length&&j<=t.length)
	{
		if(j==0||s.ch[i-1]==t.ch[j-1])
		{
			++i;++j;
		}
		else
			j=t.next[j];
	}
	if(j>t.length) return i-t.length;
	else return 0;
}

void main()
{
	sstring s,s1;
	char * c1="acabaabaabcacaabc";
	char * c2="abaabc";
	assign(s,c1);
	assign(s1,c2);
cout<<index_kmp(s,s1,1)<<endl;


}