matchall.cpp

一个值得学习的模式匹配改进的KMP算法

#include<iostream>
#include<string>
#include<fstream>
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;
	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  PrintString( )const;
	int  Match(String& t,int &i);
	void Prefix();
	void ModifiedPrefix();
	//private:
	char *str; 
	int  size;  
	int  *pre; //前缀函数数组
};

String::String(char *s)
{
	int n;
	n=strlen(s)+1;
	//为字符数组分配空间
	str=new char[n];
	//若空间分配失败则抛出异常
	if (str==0)  throw NoMem();
	size=n;
	//将字符串拷贝到本对象字符数组中
	strcpy(str,s);
	//为前缀函数数组分配空间
	pre=new int[size];
	if  (pre==0)   throw  NoMem();
}

String::String(const String& s)
{
	int n;
	n=s.size;
	//为本对象的字符数组分配空间
	str=new char[n];
	if (str==0)  throw NoMem();
	size=n;
	//将对象s的字符数组拷贝到本对象的字符数组中
	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)
{
	//若本对象字符数组空间不等于s的字符数组空间
	if (size!=s.size)
	{
		//删除本对象字符数组空间
		delete []str;
		//为本对象分配一块与s的字符数组同等大小的空间
		str=new char[s.size];
		if (str==0)  throw  NoMem();
		size=s.size;
	}
	//将s的字符数组拷贝到本对象的字符数组中
	strcpy(str,s.str);
	//返回赋值后的本类对象
	return *this;
}

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

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

String String::operator+(const String& s) const
{
	//创建新串对象temp 
	String  temp;
	//释放temp的空串所占用空间
	delete  []temp.str;
	//为temp的字符数组分配空间，以存放连接后的串
	int  n=size+s.size-1;
	temp.str=new char[n];
	if (temp.str==0)    throw  NoMem( );
	temp.size=n;
	//将本对象存放的串拷贝到temp中
	strcpy(temp.str,str);
	//将s中的串连接至temp的串后
	strcat(temp.str,s.str);
	//返回串对象temp
	return  temp;
}

void String::operator+=(const String& s)
{ char *temp;
//为存放连接后的串的字符数组temp分配空间
temp=new char[size+s.size-1];
if (temp==0)  throw NoMem();
//将本对象存放的串拷贝到temp中
strcpy(temp,str);
//将s中存放的串连接至temp中串的后部
strcat(temp,s.str);
//释放本对象的数组空间,令temp成为其数组空间
delete []str;
str=temp;
size=size+s.size-1;	
}

int  String::Find(char c,int start) const
{ 
	//若start向下越界,则令start=0
	if (start<0)   start=0;
    //若start向上越界,则查找失败,返回-1
	if (start>size-1)  return -1;
    /*使用strchr函数在当前串的位置start起查找字符
    c的首次出现位置,令p指向找到的字符*/
	char *p=strchr(&str[start],c);
	//若查找失败,返回-1
	//	if (p==0)  return -1;
	//若查找成功,返回该字符所在下标
	//	return  p-str;
	int ret;
	if(p!=0)
		ret=int(p-str);
	else ret=-1;
	return ret;
}


String  String::SubStr(int index,int count)const
{ //若下标<0,则令其为0
	if (index<0)  { count+=index;  index=0; }
    //若子串的字符个数count<0,则抛出越界异常
    if (count<0)   throw OutOfBounds(); 
    /*若下标超出或等于串长,或者子串字符个数
    为0,   则返回空串对象*/
    String s;
    if (index>=size-1 || count==0)  return  s;
	/* 若子串字符个数多于串中从index开始至串尾的   字符个数,令count为串中从index开始的字符个数*/
    if (count>size-index-1)   count=size-index-1;
	//释放串对象s的字符数组空间
    delete []s.str;
	//为串对象s的字符数组分配空间
	s.str=new char[count+1];
	
	if (s.str==0)  throw NoMem();
	s.size=count+1;
	//将子串拷贝到s中并设置串结束标记’\0’
	
	char  *p,*q;  int  i;
	for ( i=0,p=s.str,q=&str[index]; i<count; i++)
		*p++=*q++;
	*p=0;
	//返回存放子串的串对象s
	return s;
}


void  String::Insert(const String &s,int index)
{
	//若插入位置向下越界,则令其为0
	if (index<0)  index=0;
	//若插入位置向上越界,则令其为串尾位置
	if (index>size-1)  index=size-1;
	//为字符数组temp分配空间,以存放插入后的串
	char *temp;
	temp=new char[size+s.size-1];   
	if (temp==0)  throw NoMem();
	//将当前串的前index个字符拷贝到temp中
	char *p,*q;  int i;
	for (i=0,p=temp,q=str; i<index; i++)
		*p++=*q++;
	//将s中存放的串放至temp中
	strcpy(p,s.str);
	p+=s.size-1;
	/*若当前串除前index个字符外还有字符,将
	剩余字符放至temp中*/
	strcpy(p,&str[index]);
	
	delete []str;
	str=temp;
	size=size+s.size-1;
}

void  String::Delete(int index,int count)
{ //若被删字符数count<0,则抛出异常
    if (count<0)  throw OutOfBounds();
    /*若被删位置向上越界或被删字符数为0,则 
	不做任何删除操作*/
    if (index>=size-1 || count==0)  return;
	/*若被删位置向下越界,则令被删字符数减少
	并令被删位置为0*/
    if (index<0)  { count+=index; index=0; }
	/*若被删字符数count多于串中从位置index开始的所有字符,则令count为串中从index开始的字符数目*/
    if (count>size-index-1)  count=size-index-1;
	//为字符数组分配空间以存放删除后的串
	char *temp;
    temp=new char[size-count];
    if (temp==0)  throw NoMem();	
	
	/*将当前串的前index个字符拷贝到temp中
	并设置串结束符*/
	strncpy(temp,str,index);
	temp[index]='\0';
	/*若当前串从位置index起删除count个字符
	后还有剩余字符,则将其拷贝到temp中*/
	if (index<size-count-1)    
		strcat(temp,&str[index+count]);
	/*释放当前串对象的字符数组所占用空间,并令temp成为其数组空间*/
	delete []str;
	str=temp;
	size=size-count;
}

int String::ReadString(istream & istr,char delimiter)
{
	char temp[256];
	//从输入流中接收一系列字符至temp，以delimiter为终止符
	if (istr.getline(temp,256,delimiter))
	{ //释放本对象的字符数组空间
		delete []str;
		int n=strlen(temp)+1;
		//为本对象申请新的字符数组空间存放输入的字符
		str=new char[n];
		if (str==0)  throw NoMem();
		size=n;
		//将temp中字符串拷贝到当前串中
		strcpy(str,temp);
		//返回接收到的字符数
		return size-1;
	}
	//若字符接收失败,则返回-1	
	else return -1;  
} 



void String::PrintString()const
{cout<<str<<endl;}

void String::Prefix()
{
	int m=Length();
	delete[]pre;
	pre=new int[m+1];
	if (pre==0)throw NoMem();
	pre[0]=0;
	int k=0;
	for (int i=1;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;
}
int String::Match(String&t,int &i)
{   
	int j=0;
    int n=Length(),m=t.Length();     
	t.ModifiedPrefix();
	while( (i<=n)&& (j<m) )
	{
		if (str[i-1]==t.str[j])
		{
			i++;
			j++;
		}
		else 
			if(j==0)i++;
			else j=t.pre[j-1];
	}
	if(j<m)
		return 0;
	else
		return i-m;
}

void Mov(int Temp,int n,int flag[])
{
	for(int i= 1;i<= n;i++)
		if(flag[i]== 0)
		{
			flag[i]= Temp;
			return;
		}
}

int main()
{
	int n,m,i;
	string str1,str2;
	ifstream in("input.txt");
	getline(in,str1);
	getline(in,str2);
	
	n=str1.length()+1;
	m=str2.length()+1;
	int *flag= new int[n];
	for(i= 1;i<= n-1;i++) flag[i]=0;
	String Str1,Str2;
	
	Str1.str=new char[n];
	Str1.size=n;
	for(i= 0;i<n-1;i++) Str1.str[i]=str1.at(i);
	Str2.str=new char[m];
	Str2.size=m;
	for(i= 0;i<m-1;i++) Str2.str[i]=str2.at(i);
	
	i= 1;
	while(i<= n-1)
	{
		int Temp= Str1.Match(Str2,i);
		if(Temp!= 0)
		{
			Mov(Temp,n-1,flag);
			i= Temp+1;
		}
	}
	ofstream out("output.txt");
	if (flag[1]==0)
		out<<"0";
    else
		for(i= 1;i<= n-1;i++)
			if(flag[i]!= 0)
				out<<flag[i]<<" ";
			return 0;
}