matchall.cpp

设计一个算法

#include<string.h>
#include<fstream.h>
class String
{
   public:
	   String(char *s=""); //构造函数 
	   String(const String & s);
	   ~String();//析构函数
	   int Length() const;//串长运算 
	   void Prefix();
	   void Match(String & t);
	   void setup(char tmp[]);
   private:
	   int *pre;//前缀函数数组
	   char *str;//串数组
	   int size;
};
int String::Length() const
{
	return size-1;
}
String::String(char *s)
{
	size=strlen(s)+1;
	str=new char [size];
	strcpy(str,s);
	pre=new int [size];
}
String::~String()
{
	delete [] str;
	delete [] pre;
} 
void String::setup(char tmp[])
{
	delete [] str;
	size=strlen(tmp)+1;
	str=new char [size];
	strcpy(str,tmp);
}
void String::Match(String & t)
{
	int i=1,j=0,x=1;
	int n=Length(),m=t.Length();
	t.Prefix();
	ofstream outfile("output.txt");
    if(!outfile)
	{
	  cout<<"Error opening file for writing\n";
	  return;
	}
    while((i<=n)&&(j<m))
	{
		if(str[i-1]==t.str[j]){
			i++;
			j++;
		}
		else
			if(j==0) i++;
			else j=t.pre[j];
		if(j==m)
		{
		outfile<<i-m<<" ";
		i=i-m+1;
		j=0;
		x=0;
		}
	}
		if(x==1) outfile<<" ";
	outfile.close();
}
void String::Prefix()
{
	int m=Length();
	delete [] pre;
	pre=new int [m+1];
	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;
	}
}
char tmp1[100000];
char tmp2[10000];
main()
{	 
	String s,t;
	ifstream infile("input.txt");
    if(!infile)
	{  
	cout<<"Error opening file for reading\n";
    return 0;
	}
	infile.getline(tmp1,100000,'\n');
	s.setup(tmp1);
    infile.getline(tmp2,1000,'\n');
	t.setup(tmp2);
	s.Match(t);
	return 0;
}