gap.cpp

这是一个关于间隙字符串匹配问题的程序

#include <iostream.h>
#include <fstream.h>
#include <string.h>
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; 
    int Find(char c, int start) const; 
    String SubStr(int start, int count) const; 
	void Delete(int start, int count); 
	void Prefix( ); 
	void ModifiedPrefix( ); 
	int Match(String& t,int start); 
private: 
	char *str;  
	int  *pre;  
	int  size;  
};
String::String(char *s) 
{
	size = strlen(s) + 1; 
    str = new char [size]; 
    strcpy(str,s);
	pre=new int[size];
} 
String::String(const String& s) 
{ 
	size = s.size; 
    str = new char [size]; 
    strcpy(str,s.str); 
	pre=new int[size];
 } 
String::~String( ) 
{ 
    delete [ ] str; 
	delete [ ] pre; 
} 
String& String::operator= (const String& s) 
{ 
	if (s.size != size)
    { 
		delete [ ] str; 
        str = new char [s.size]; 
        size = s.size; 
    } 
    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; 
} 


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

String String::SubStr(int start,  int count) const 
{ 
	int Left = size- start ,i; 
	String temp; 
	char *p, *q; 
	if (start >= size) return temp; 
    if (count > Left) count = Left; 
	delete [ ] temp.str; 
    temp.str = new char [count+1]; 
	for(i=0,p=temp.str,q=&str[start-1];i < count;i++) *p++ = *q++; 
	*p = 0; 
	temp.size = count+1; 
    return temp; 
} 
int String::Find(char c, int start) const
{ 
    int ret; 
	char *p; 
	p = strchr(&str[start-1],c);
    if (p != 0)  ret = int(p-str+1); 
	else  ret = -1; 
	return ret; 
} 
void String::Prefix() 
{  
	delete [ ] pre; 
    int m=Length();    
	pre = new int [m+1]; 
	int k=0;   
	pre[1]=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; 
   } 
} 
int String::Match(String& t,int start) //我在这里对MATCH进行了修改，start为主串开始匹配的位置
{
    int i=start,j=0;                  //这样，i就可以回溯到我们想要它开始匹配的位置，不必调用删除
	int n=Length(), m=t.Length(); 
	t.Prefix(); 
    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) return 0; 
	else return i-m; 
} 
void main()
{   ifstream in("input.txt");
    ofstream out("output.txt");
    int i=0,j,start=1;
	char a[60000],b[60000],c[30000];
	in>>a;
	in>>b;
	String s1(a);
    String s2(b);
	String s3(c);
    while(i!=(-1))
	{
	i=s2.Find('*',1);
	s3=s2.SubStr(1,i-1);
	j=s1.Match(s3,start);
    if(j==0)
	{break;
	goto judge;
	}
	else 
	{
		s2.Delete(0,i);   //由于匹配子串不同，前缀也发生了变化，所以s2的前i项一定要删除
		start=i+j-1;
        i=s2.Find('*',1);
	}
	}
	j=s1.Match(s2,start);
	goto judge;

judge:
if(j!=0)
   out<<"Yes";
else 
   out<<"No";
}