论坛 › C/C++ › 间隙字符串匹配问题（c++)

lynnyan 发表于 2005-4-22 01:37

间隙字符串匹配问题（c++)

<P>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>
<P>[**** Hidden Message *****</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
class String
{
  public:
String(char *s="");
String(const String&amp; s);
~String();
int Length() const;
int ReadString();
int Rs();
void Prefix();
void ModifiedPrefix();
int Match(int i,String&amp; t);
  private:
   char *str;
   int *pre;
   int size;
};
String::String(char *s)
{
size=strlen(s)+1;
str=new char;
if(str==0)
  throw "error";
strcpy(str,s);
pre=new int;
if(pre==0)
  throw "error";
}
String::String(const String&amp; s)
{
size=s.size;
str=new char ;
if(str==0)
  throw "error";
strcpy(str,s.str);
pre=new int ;
if(pre==0)
  throw "error";
}
String::~String()
{
delete [] str;
delete [] pre;
}
int String::Length() const
{
return size-1;
}
int String::ReadString()
{
char tmp;
    if(in&gt;&gt;tmp)
{
  delete [] str;
  size=strlen(tmp)+1;
  str=new char ;
  strcpy(str,tmp);
  return size-1;
}
else
  return -1;
}
int String::Rs()
{
char tmp,c;
int i=0;
while(in&gt;&gt;c)
{
  if(c!='*')
  tmp=c;
  else if(c=='*'&amp;&amp;i&gt;0)
   break;
}
if(i&gt;0)
{
  delete [] str;
  size=i+1;
  str=new char;
  if(str==0)
   throw "error";
  for(i=0;i&lt;size-1;i++)
      str=tmp;  
  return size-1;
}
else
  return -1;
}
void String::Prefix()
{
int m=Length();
delete [] pre;
pre=new int ;
pre=0;
int k=0;
for(int i=2;i&lt;=m;i++)
{
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
   k=pre;
         if(*(str+i-1)==*(str+k))
    pre=++k;
   else
    pre=0;
}
}
void String::ModifiedPrefix()
{
int *f;
int m=Length();
f=new int;
Prefix();
for(int i=1;i&lt;=m;i++)
{
    f=pre;
}
for(i=1;i&lt;m;i++)
{
  int k=f;
  if((k==0)||(*(str+i)!=*(str+k)))
   pre=k;
  else
   pre=pre;
}
delete []f;
}
int String::Match(int i,String&amp; t)
{
int j=0;
int n=Length(),m=t.Length();
t.ModifiedPrefix();
while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str==t.str)
  {
   i++;
   j++;
  }
  else
   if(j==0)
        i++;
      else
    j=t.pre;
  if(j&lt;m)
   return 0;
  else
   return i-1;
}
int main()
{
if(in.fail())
{
  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
int i=1;
String s,t;
s.ReadString();
while(t.Rs()+1)
{
  i=s.Match(i,t);
  if(!i)
  {
      out&lt;&lt;"No"&lt;&lt;endl;
   break;
  }
}
if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
return 0;
}

zidance 发表于 2007-3-16 23:03

看看啊

sgnswb 发表于 2007-4-2 09:59

顶

ari0101 发表于 2007-4-3 11:30

谢谢

hyacinth13 发表于 2007-4-5 19:56

<p>谢啦~~</p>

zhaoyunfei1126 发表于 2007-4-7 11:39

好吧

ottiou 发表于 2013-5-11 16:12

看看看看看看看看

查看完整版本: 间隙字符串匹配问题（c++)