a.cpp

给定两个串S和T

#include<iostream.h>
#include<string.h>
#include<assert.h>
class String
{
public:
	char *str;
	String(char *s)               //创建一个初值为s的字符串
	{
		str=new char[strlen(s)+1];
		assert(str!=NULL);        //开辟空间不成功时，运行异常，退出
		strcpy(str,s);            //用标准字符串函数strcpy，将s完全复制到指针str所指的存储空间
	}
	~String()                     //消除该串实例
	{
		delete []str;             //释放动态存储空间
	}
	const char& operator[](int n)const
	{
		return str[n];
	}
	int Strlen()                  //返回串的长度
	{
		int i=0;
		while(str[i]!=0) i++;
		return i;
	}
};
int *Next(String P)
{
	int m=P.Strlen();             //m为模板P的长度
	assert(m>0);                  //若m＝0，退出
	int *N=new int[m];
	N[0]=0;
	for(int i=1;i<m;i++)          //分析P的每个位置i
	{
		int k=N[i-1];             //第(i-1)位置的最长前缀串长度
		//以下while语句递推决定合适的前缀位置k
		while(k>0&&P.str[i]!=P.str[k])
		{
			k=N[k-1];
			//根据P[i]比较第k位置前缀字符，决定N[i]
			if(P.str[i]==P.str[k]) N[i]=k+1;
			else N[i]=0;
		}
	}
	return N;
}
int KMP_FindPat(String S,String P,int *N,int startindex)
{
	//事先已经计算出P的特征数组N，作为输入参数
	//S末尾再倒数一个模板长度位置
	int LastIndex=S.Strlen()-P.Strlen();
	if(startindex>LastIndex)
	{
		return -1;                //startindex过大，匹配无法成功
	}
	int i;                        //i是指向S内部字符的游标
	int j=0;                      //j是指向P内部字符的游标
	for(i=startindex;i<S.Strlen();i++)    //S游标i循环加1
	{
		while(P.str[j]!=S.str[i]&&j>0)
			j=N[j-1];
		if(P.str[j]==S.str[i]) j++;       //P[j]与S[i]相同，继续循环
		if(j==P.Strlen())         //匹配成功，返回该S子串的开始位置
			return(i-j+1);
	}
	return -1;                    //P和S整个匹配失败，函数返回值为负
}
int main()
{
	String s("BAAABBBAA");
	cout<<s.Strlen();
	String t("BAAABBBCDDCBBBAAABBBDD");
	int m=s.Strlen();
	int i,*M=new int[m];
	M=Next(s);
	for(i=0;i<m;i++) cout<<M[i]<<" ";
	cout<<endl;
	return 0;
}