所有匹配.cpp

字符串匹配问题

#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

class NoMem{};
class OutOfBounds{};

class String{
public:
	String(char *s="");
	String(const String& s);
	~String();
	String &operator=(const String &s);
	bool operator==(const String &s) const;
	int Length() const{return size-1;}
	String operator+(const String &s) const;
	void operator+=(const String &s);
	int Find(char c,int start) const;
	String SubStr(int index,int count) const;
	void Insert(const String &s,int index);
	void Delete(int index,int count);
	int ReadString(istream &is=cin,char delimiter='\n');
	void Prefix();
	void ModifiedPrefix();
	void Match(String &t,ostream &out=cout);
private:
	char *str;
	int *pre;
	int size;
};

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

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;
}

String &String::operator=(const String &s){
	if(s.size!=size){
		delete[] str;
		str=new char[s.size];
		if(str==0)
			throw NoMem();
		size=s.size;
	}
	strcpy(str,s.str);
	return *this;
}

bool String::operator==(const String &s) const
{
	return strcmp(str,s.str)==0;
}

String String::operator+(const String &s) const{
	String temp;
	int n;
	delete[] temp.str;
	n=size+s.size-1;
	temp.str=new char[n];
	if(temp.str==0)
		throw NoMem();
	temp.size=n;
	strcpy(temp.str,str);
	strcat(temp.str,s.str);
	return temp;
}

void String::operator+=(const String &s){
	char *tempstr;
	int n;
	n=size+s.size-1;
	tempstr=new char[n];
	if(tempstr==0)
		throw NoMem();
	strcpy(tempstr,str);
	strcat(tempstr,s.str);
	delete[] str;
	str=tempstr;
	size=n;
}

int String::Find(char c,int start) const{
	if(start<0) start=0;
	if(start>size-1) return -1;
	int ret;
	char *p;
	p=strchr(&str[start],c);
	if(p!=0)
		ret=int(p-str);
	else ret=-1;
	return ret;
}

String String::SubStr(int index,int count) const{
	if(index<0){
		count+=index;
		index=0;
	}
	if(count<0)
		throw OutOfBounds();
	int Left=size-index-1,i;
	String temp;
	char *p,*q;
	if(index>=size-1)
		return temp;
	if(count>Left) count=Left;
	delete[] temp.str;
	temp.str=new char[count+1];
	if(temp.str==0)
		throw NoMem();
	for(i=0,p=temp.str,q=&str[index];i<count;i++)
		*p++=*q++;
	*p=0;
	temp.size=count+1;
	return temp;
}

void String::Insert(const String &s,int index)
{
	if(index<0)
		index=0;
	if(index>size-1)
		index=size-1;
	int n,m=s.size-1,i;
	char *newstr,*p,*q;
	n=size+m;
	newstr=new char[n];
	if(newstr==0)
		throw NoMem();
	for(i=0,p=newstr,q=str;i<=index-1;i++)
		*p++=*q++;
	strcpy(p,s.str);
	p+=m;
	strcpy(p,&str[index]);
	delete[] str;
	size=n;
	str=newstr;
}

void String::Delete(int index,int count){
	if(count<0)
		throw OutOfBounds();
	if(index>=size-1||count==0) return;
	if(index<0){
		count+=index;
		index=0;
	}
	int Left=size-index-1,n,i;
	char *newstr,*p,*q;
	if(count>Left)
		count=Left;
	n=size-count;
	newstr=new char[n];
	if(newstr==0)
		throw NoMem();
	for(i=0,p=newstr,q=str;i<=index-1;i++)
		*p++=*q++;
	q+=count;
	strcpy(p,q);
	delete[] str;
	size=n;
	str=newstr;
}

int String::ReadString(istream &istr,char delimiter)
{
	char tmp[256];
	if(istr.getline(tmp,256,delimiter))
	{
		delete[] str;
		size=strlen(tmp)+1;
		str=new char[size];
		if(str==0)
			throw NoMem();
		strcpy(str,tmp);
		return size-1;
	}
	else return -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 m=Length();
	Prefix();
	for(int i=1;i<m;i++){
		int k=pre[i];
		if((k==0)||(*(str+i)!=*(str+k))) pre[i]=k;
		else pre[i]=pre[k];
	}
}

void String::Match(String &t,ostream &out){
	int i=0,j=0;
	int n=Length(),m=t.Length();
	t.ModifiedPrefix();
	while(i<=n-m+j){
		while(j<m&&i<n)
			if(str[i]==t.str[j]){
				i++;
				j++;
			}
			else
				if(j==0) i++;
				else j=t.pre[j];
		if(j==m)
			out<<i+1-m<<" ";
		j=t.pre[m];
	}
}

void main(){
	String s,t;
	fstream infile("input.txt",ios::in);
	fstream outfile("output.txt",ios::out);
	s.ReadString(infile);
	t.ReadString(infile);
	s.Match(t,outfile);
	cout<<"程序结束。"<<endl;
}