matchall.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

 #include<iostream>
#include<fstream>
#include<string>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

class NoMem
{
public:
	NoMem(){;}
};


class String
{
public:
	String(char*s="");
	String(const String& s);
	~String();
	int Length()const;
	void Prefix();
	void ModifiedPrefix();
	void Matchall(String& t);
private:
	char *str;
	int *pre;
	int size;
};

String::String(char *s)
{
	size=strlen(s)+1;
	str=new char[size];
	if(str==0)
		throw NoMem();
	strcpy(str,s);
	pre=new int[size];
	if(pre==0)
		throw NoMem();
}

String::String(const String& s)
{
	size=s.size;
	str=new char[size];
	if(str==0)
		throw NoMem();
	strcpy(str,s.str);
	pre=new int[size];
	if(pre==0)
		throw NoMem();
}

String::~String()
{
	delete[]str;
	delete[]pre;
}

int String::Length()const
{
	return size-1;
}

void String::Prefix()
{
	int m=Length();
	delete[]pre;
	pre=new int[m+1];
	if(pre==0)
		throw NoMem();
	pre[1]=0;
	int k=0;
	for(int i=2;i<=m;i++)
	{
		while((*(str+i-1)!=*(str+k))&&(k>0))
			k=pre[k];
		if(*(str+i-1)==*(str+k))
			pre[i]=++k;
		else
			pre[i]=0;
	}
}

void String::ModifiedPrefix()
{
	int *f;
	int m=Length();
	f=new int[m+1];
	Prefix();
	for(int i=1;i<=m;i++)
		f[i]=pre[i];
	for( i=1;i<m;i++)
	{
		int k=f[i];
		if((k==0)||(*str+i)!=*(str+k))
			pre[i]=k;
		else
			pre[i]=pre[k];
	}
	delete[]f;
}

void String::Matchall(String& t)
{
	int i=1,j=0,count=0;
	int n=Length(),m=t.Length();
	t.ModifiedPrefix();
	while(i<=n)
	{
		if(str[i-1]==t.str[j])
		{
			i++;
			j++;
		}
		else
			if(j==0)
				i++;
			else
				j=t.pre[j];
		if(j==m)
		{
			out<<i-m<<' ';
			count++;
		}
	}
	if(count==0)//找不到匹配模式串
		cout<<" ";
}

int main()
{
	char *s, *t;int M=50000,N=40000;
	s=new char[M];//主串
	t=new char[N];//模式串
	in>>s>>t;
	String S(s);
	String T(t);
	S.Matchall(T);
    return 0;
}