string.cpp

由于简单模式匹配算法在一次字符比较失败后

#include "tou.h"
#include<string.h>
#include<assert.h>
#include<iostream.h>
char nothing;//放空字符的全局变量
//int isLowerCase(char);
//int isUpperCase(char);

/////////////////////////////////////////////////////////////////////
string::string(unsigned size)
{
	assert(size>=0);
	buflen=1+size;
	buffer=new char[buflen];
	assert(buffer!=0);
	for(unsigned i=0;i<buflen;i++)
		buffer[i]='\0';
}
string::string(const char* inittext)
{
	buflen=1+strlen(inittext);
	buffer=new char[buflen];
	assert(buffer!=0);
	for(unsigned i=0;inittext[i]!='\0';i++)
		buffer[i]=inittext[i];
	buffer[i]='\0';
}
string::string(const string & initstr)
{
	buflen=1+strlen(initstr.buffer);
	buffer=new char[buflen];
	assert(buffer!=0);
	for(unsigned i=0;initstr.buffer[i]!='\0';i++)
		buffer[i]=initstr.buffer[i];
	buffer[i]='\0';
}
string::string(char c)
{
	buflen=2;
	buffer=new char[buflen];
	assert(buffer!=0);
	buffer[0]=c;
	buffer[1]='\0';
}
string::string()
{
	buflen=1;
	buffer=new char[buflen];
	assert(buffer!=0);
	buffer[0]='\0';
}
string::~string()
{
	delete []buffer;
	buffer=0;
}
unsigned string::length()const
{
	return strlen(buffer);
}
void string::operator=(const string & right)
{
	const unsigned rightLength=right.length();
	if(right.length()>=buflen)
	{
		delete []buffer;
		buflen=1+rightLength;
		buffer=new char[buflen];
		assert(buffer!=0);
	}
	for(unsigned i=0;right.buffer[i]!='\0';i++)
		buffer[i]=right.buffer[i];
	buffer[i]='\0';
}
void string::operator=(const char*st)
{
    const unsigned stLength=strlen(st);
	if(strlen(st)>=strlen(buffer))
	{
		delete []buffer;
		buflen=1+stLength;
		buffer=new char[buflen];
		assert(buffer!=0);
	}
	for(unsigned i=0;st[i]!='\0';i++)
		buffer[i]=st[i];
	buffer[i]='\0';
}
void string::operator=(const char ch)
{
	buflen=2;
	buffer=new char[buflen];
	assert(buffer!=0);
	buffer[0]=ch;
	buffer[1]='\0';
}
void string::operator+=(const string & v)
{
	unsigned i;
	unsigned conlen=length()+v.length();
	if(conlen>=buflen)
	{
		char *newbuf=new char[1+conlen];
		assert(newbuf!=0);
		for(i=0;buffer[i]!='\0';i++)
			newbuf[i]=buffer[i];
		delete []buffer;
		buflen=1+conlen;
		buffer=newbuf;
	}
	else 
		i=strlen(buffer);
	for(unsigned j=0;v.buffer[j]!='\0';i++,j++)
		buffer[i]=v.buffer[j];
	buffer[i]='\0';
}
string operator+(const string&left,const string&right)
{
	string result(left);
	result+=right;
	return result;
}
void string::operator+(const char* st)
{
	unsigned i;
	unsigned conlen=length()+strlen(st);
	if(conlen>=buflen)
	{
		char *newbuf=new char[1+conlen];
		assert(newbuf!=0);
		for(i=0;buffer[i]!='\0';i++)
			newbuf[i]=buffer[i];
		delete []buffer;
		buflen=1+conlen;
		buffer=newbuf;
	}
	else 
		i=strlen(buffer);
	for(unsigned j=0;st[j]!='\0';i++,j++)
		buffer[i]=st[j];
	buffer[i]='\0';
}
void string::operator+(const char ch)
{
	unsigned i;
	unsigned conlen=length()+1;
	if(conlen>=buflen)
	{
		char *newbuf=new char[1+conlen];
		assert(newbuf!=0);
		for(i=0;buffer[i]!='\0';i++)
			newbuf[i]=buffer[i];
		delete []buffer;
		buflen=1+conlen;
		buffer=newbuf;
	}
	else 
		i=strlen(buffer);
		buffer[i]=ch;
	buffer[i+1]='\0';

}
char & string::operator[](unsigned index)const
{ 
	if(index>=(int)strlen(buffer))
	{
		nothing='\0';
		return nothing;
	}
	return buffer[index];
}

int string::compare(const string & val)const
{
	char*p=buffer;
	char*q=val.buffer;
	for(;(*p!='\0')&&(*p==*q);p++,q++)
		;
	return *p-*q;
}
string::operator  const char*()const
{
	return buffer;
}
istream & string::getline(istream & in)
{
	in.getline(buffer,buflen,'\n');
	return in;
}
istream & operator>>(istream & in,string & str)
{
	char inbuffer[1000];
	if(cin.getline(inbuffer,1000,'\n'))
		str=inbuffer;
	else 
		str="";
	return in;
}
int operator<=(const string & left,const string & right)
{
	return left.compare(right)<=0;
}
int operator>=(const string & left,const string & right)
{
	return left.compare(right)>=0;
}
int operator==(const string & left,const string & right)
{
	return left.compare(right)==0;
}
int operator!=(const string & left,const string & right)
{
	return left.compare(right)!=0;
}
int operator<(const string & left,const string & right)
{
	return left.compare(right)<0;
}

///////////////////////////////////////////////////////////////////////////////////////
substring::substring(string & base,unsigned start,unsigned len)
:base(base),start(start),len(len)
{}
substring::substring(const substring& source)
:base(source.base),start(source.start),len(source.len)
{}
void substring::operator=(const string & rstr)const
{//如复制长度相等，可直接进行
	unsigned i;
	if(len==rstr.length()){
		for(i=0;i<len;i++)
			base[start+i]=rstr[i];
		return;
	}
	//计算新串长度
	unsigned newlen=rstr.length()+base.length()-len;
	char*newdata=new char[newlen+1];
	//复制 
	for(i=0;i<start;i++)
		newdata[i]=base[i];
	for(unsigned j=0;rstr[j]!='\0';j++)
		newdata[i++]=rstr[j];
	for(unsigned k=start+len;base[k]!='\0';k++)
		newdata[i++]=base[k];
	newdata[i]='\0';
	//替换缓冲区
	delete []base.buffer;
	base.buffer=newdata;
	base.buflen=newlen;
	return;
}
substring::operator string()const
{
	char*buf=new char[len+1];
	assert(buf!=0);
	for(unsigned i=0;i<len;i++)
		buf[i]=base[start+i];
	buf[len]='\0';
	string result(buf);
	delete []buf;
	buf=0;
	return result;
}
substring string::operator ()(unsigned start,unsigned len)
{
	if(start>=length()){
		start=0;
		len=0;
	}
	int maxlen=length()-start;
	if(len>maxlen)len=maxlen;
	return substring(*this,start,len);
}
///////////////////////////////////////////////////////////////////////
stringMatcher::stringMatcher(string& t):text(t)
{
	pos=0;
}
int stringMatcher::init()
{
	pos=-1;
	return operator++();
}
int stringMatcher::operator!()const
{
	return(pos>=0)&&pos<(text.length());
}
substring stringMatcher::operator ()()
{
	return text(position(),length());
}
unsigned stringMatcher::position()const
{
	return pos;
}
void stringMatcher::position(unsigned p)
{
	pos=p;
}
unsigned stringMatcher::length()
{
	return patlen;
}
///////////////////////////////////////////////////////////////////////////////
int SimpleStrMatcher::operator++()
{
	unsigned last=text.length()-patlen;
	for(pos++;pos<=last;pos++)
		if(pattern==string(text(pos,patlen)))
			return 1;
		pos=-1;
		return 0;
}
SimpleStrMatcher::SimpleStrMatcher(const string &p,string& t):stringMatcher(t),pattern(p)
{
	patlen=p.length();
}
//////////////////////////////////////////////////////////////////////////////////////// 
KMPStrMatcher::KMPStrMatcher(const string&p,string&t):stringMatcher(t),pattern(p)
{
	patlen=p.length();
	assert(patlen>0);
	prefix=new int[patlen];
	assert(prefix!=0);
	prefix[0]=0;
	for(unsigned i=1;i<patlen;i++){
		unsigned k=prefix[i-1];
		while(pattern[i]!=pattern[k]&&k!=0)
			k=prefix[k-1];
		if(pattern[i]==pattern[k])
			prefix[i]=k+1;
		else 
			prefix[i]=0;
	}
}
int KMPStrMatcher::operator++()
{
	unsigned end=text.length();
	unsigned cur=pos+1;
	unsigned patp=0;//模式中的位置
	for(;cur<end;cur++)
	{
		while(patp>0&&pattern[patp]!=text[cur])
			patp=prefix[patp-1];
		if(pattern[patp]==text[cur])
			if(++patp==patlen)
			{
				pos=1+cur-patlen;
				return 1;
			}
	}
	pos=-1;
	return 0;
}
KMPStrMatcher::~KMPStrMatcher()
{
	delete []prefix;
	prefix=NULL;
}

void main()
{
  string text,str1,str2;	
  cout<<"请输入一段文字："<<'\n';
  cin>>text;
  cout<<"请输入要替换的文字"<<'\n';
  cin>>str1;
  
  KMPStrMatcher mat(str1,text);
  if(mat.init())
  {
	  cout<<"请输入要替换为哪些文字"<<'\n';
        cin>>str2;
     for(;!mat;mat++)
	 {
		 cout<<"found match at:"<<mat.position()<<endl;
         text(mat.position(),str1.length())=str2;
	 }
	cout<<text<<'\n';
  }
  else 
	  cout<<"不存在要替换的字符串！"<<'\n';	
}