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

lynnyan

<>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>
<>[

游客，如果您要查看本帖隐藏内容请回复

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
using namespace std;
6 _6 z7 ~$ E; V" O" N* M- u# n7 Bifstream in("input.txt");
' Q0 V- ]( Z; H5 ?& O- Oofstream out("output.txt");
$ D4 i  Y, T! H9 c+ v3 rclass String
{
  public:
/ D7 O4 B/ g8 Q8 g String(char *s="");
3 d, w& X5 }- N- H! ?( l# v! j String(const String&amp; s);
~String();
% v- d" x" t+ T* ]* y6 D+ U int Length() const;
int ReadString();
int Rs();
! a% W5 f+ N( ~7 d6 M1 }) l( ] void Prefix();
  ~$ c; p$ M+ l! E" L void ModifiedPrefix();
int Match(int i,String&amp; t);
. K$ c& Y5 I. o( j  private:
   char *str;
0 O$ r9 V+ L7 O6 u. Q   int *pre;
   int size;
6 Z: I5 q8 _# _5 f};
5 e/ I/ C& P: [" V2 q" jString::String(char *s)
2 B: ?& V9 `, n* D& U6 j- F6 d{
# |, Z7 l+ Q. C) w+ X+ \8 `2 ` size=strlen(s)+1;
( S* T7 ^3 L* o0 ^2 s; X/ e str=new char[size];
3 y/ [9 V) S6 b  e9 v2 _8 e( ] if(str==0)
& o: N- O/ u  A7 w; u% |! x# O9 @) s  throw "error";
) z; L) D' P, U$ q% d strcpy(str,s);
7 U" r- e) F4 d pre=new int[size];
if(pre==0)
  throw "error";
}
String::String(const String&amp; s)
{
/ U  r  ]& J% N8 \: d size=s.size;
str=new char [size];
if(str==0)
  throw "error";
strcpy(str,s.str);
( b+ |1 k4 `5 k+ D; a pre=new int [size];
7 o/ Q9 K( A9 G if(pre==0)
  throw "error";
}
) K0 T% B1 o- C! o; a& ^, C: I" A, ~String::~String()
( N: c4 B& r; _% Z9 g1 @{
delete [] str;
delete [] pre;
}
int String:ength() const
" D0 o( c  H3 U{
return size-1;
# B4 o& T" g' o* }}
int String::ReadString()
{
char tmp[256];
( S* F  j+ ?, r' z* e8 l$ {* |* u    if(in&gt;&gt;tmp)
{
  delete [] str;
# @, ^( X1 O, t9 l5 o  size=strlen(tmp)+1;
0 A! `3 l  w/ p. _6 l  str=new char [size];
  strcpy(str,tmp);
* T" y6 e, |& G7 v+ w: s  return size-1;
* Y: V6 _- s/ b; O" | }
) X: V9 m, s8 f, I5 ]$ q, s" ^ else
6 G! u4 i3 k- X9 L- Z% ~  return -1;
}
int String::Rs()
- m8 Z( V$ _3 k& m( U{
char tmp[256],c;
% g  d+ E; y6 b  u) `: g6 |2 F  p int i=0;
while(in&gt;&gt;c)
{
  if(c!='*')
+ s; [' Z6 w: j  tmp[i++]=c;
% d$ r' h1 x2 }: m  o  else if(c=='*'&amp;&amp;i&gt;0)
4 B: k  Z% ~# s0 K6 J# P   break;
5 \4 u5 A: B! G7 r3 a9 M }
# \0 N1 h7 e+ E- R. t0 _ if(i&gt;0)
{
  o9 j" P* |# n1 z- H% g* ~! r  delete [] str;
$ x, L. R2 V' E) L' B2 J  size=i+1;
: ^2 ?5 S: s7 [8 N* n4 I% i) _0 ?1 o  str=new char[size];
  if(str==0)
   throw "error";
1 W( ~7 U5 ^9 d2 |4 g  for(i=0;i&lt;size-1;i++)
      str=tmp;  
  return size-1;
7 n4 q# V, w4 x$ ?8 w3 K. f }
else
1 O2 d% T+ V9 |  return -1;
/ S% l% G) `. l; h/ N: h& m+ c}
void String:refix()
{
7 r! n* x2 I4 ~ int m=Length();
delete [] pre;
, K; f1 Z) A( e& p# V5 }% o# ^ pre=new int [m+1];
pre[1]=0;
int k=0;
( z+ ]1 o" m2 s8 U5 k$ b for(int i=2;i&lt;=m;i++)
3 Q+ J4 `* _/ ^( } {
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
   k=pre[k];
0 c" y/ C0 M% a- Z) J# `         if(*(str+i-1)==*(str+k))
    pre=++k;
7 L% k8 S& V. ^+ \7 ?, g   else
, T8 J2 B3 S" j1 v5 }    pre=0;
4 ~6 i+ u/ J8 R }
}
void String::ModifiedPrefix()
) ~% N$ v, m. D. C5 R{
int *f;
' ^. O+ l/ |# P int m=Length();
f=new int[m+1];
1 N1 G# Z4 z9 G- Y& ^( E% p Prefix();
# v- C4 c+ W' c: ^8 Z4 f for(int i=1;i&lt;=m;i++)
{
    f=pre;
! u6 ?) \; v1 P5 w9 y1 ]* [ }
for(i=1;i&lt;m;i++)
* N* A3 o8 M0 g) R1 y( N. U {
  int k=f;
$ y2 P; y3 w# {& k/ O5 T  if((k==0)||(*(str+i)!=*(str+k)))
6 }5 ^( @0 G* n& b# X4 P# I1 Y   pre=k;
  else
   pre=pre[k];
) s6 z' F9 e+ @4 y }
$ ]. w5 Q, z6 @+ Q" [ delete []f;
) l# z# V$ _, _" \: Y" d}
  Y- ]0 J7 z* D. N( sint String::Match(int i,String&amp; t)
{
5 f5 q$ b& Z- p6 Y) U int j=0;
int n=Length(),m=t.Length();
t.ModifiedPrefix();
while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
. m; f6 ~/ M+ {* a  {
   i++;
   j++;
; q7 ?3 H# z6 {% k+ ]% H  }
  else
   if(j==0)
# o4 v% S4 y% ~( r  p7 U0 V        i++;
# K9 Z: F& T& }& _      else
, {  g) @) X" S6 _9 Q1 ^& F+ W$ a    j=t.pre[j];
  if(j&lt;m)
   return 0;
* p* `% U7 E: a) q* c: h4 ~& I& e  else
% h, e/ [, A+ z' P   return i-1;
}
int main()
{
7 m; I. U/ L+ K0 p# d+ A+ |2 @ if(in.fail())
0 O! [. ?: U$ K3 @# l {
2 T' ~/ x9 k; _9 E) l" d  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
int i=1;
4 U, Y/ Q( P. Z String s,t;
7 T6 i# T; i# j" L s.ReadString();
while(t.Rs()+1)
1 j6 r0 S4 u) x {
  i=s.Match(i,t);
5 M7 b$ ]$ c$ G& p6 c5 B' e  if(!i)
  {
4 `- k) c9 v# p      out&lt;&lt;"No"&lt;&lt;endl;
0 j  A" i! h1 \  f1 R  Y- S9 n   break;
  }
}
if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
8 d0 e1 S( s  ^2 g& Z9 D, X; G return 0;
}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看