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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
+ H' X/ e0 t# ]% \8 M7 Dusing namespace std;
/ H: ~: {( {$ d& J3 v3 \+ N: @ifstream in("input.txt");
ofstream out("output.txt");
8 q, K- y, e, v0 Pclass String
{
3 n# `! V$ ~) P1 B0 l7 P  public:
String(char *s="");
- q# _/ P6 P8 x5 u9 ~$ O String(const String&amp; s);
~String();
5 S9 Y3 e+ v6 M! B0 m int Length() const;
int ReadString();
6 v6 y& ~% T! y/ V. M/ R, o% K int Rs();
# z) w) {5 [3 x+ } void Prefix();
% f1 Q' M% H6 ? void ModifiedPrefix();
int Match(int i,String&amp; t);
5 Y: U% f( Y. {3 v! J$ @  private:
4 }  u( H) ^; q1 h7 W   char *str;
   int *pre;
   int size;
};
String::String(char *s)
" b: `$ S) E  ^# y1 ^{
( z$ U5 Z- ^4 H1 ^. _1 O size=strlen(s)+1;
' d' e+ H0 [$ b str=new char[size];
if(str==0)
8 J# M/ i! t" S2 Y# _  throw "error";
strcpy(str,s);
& Q" }. Y: P# k% ~9 [ pre=new int[size];
8 F) s5 k4 ~. N8 K: E, n0 A if(pre==0)
  throw "error";
}
String::String(const String&amp; s)
, K5 X* n5 l: P* U: _# e0 U4 a{
- X# F1 d$ U/ R+ k+ O$ y size=s.size;
str=new char [size];
if(str==0)
4 l. o! d: ~) C: w2 ~0 N5 E$ k, B7 ^  throw "error";
strcpy(str,s.str);
+ `) h: `4 {% N& T pre=new int [size];
if(pre==0)
  throw "error";
}
String::~String()
{
' A9 U* A2 E1 n2 G( l% G delete [] str;
delete [] pre;
}
5 d9 ~9 [- J/ i- Uint String:ength() const
{
return size-1;
}
- N9 p" ?$ E( G  Zint String::ReadString()
1 q4 z, g" j0 U{
char tmp[256];
    if(in&gt;&gt;tmp)
{
1 e: S1 E& k, n3 B. D0 ^  delete [] str;
! R3 R- c5 n5 n; B) V  size=strlen(tmp)+1;
+ w) p7 {8 N" W" l. m3 i$ m+ ?  str=new char [size];
. x; B; x4 E) g. K- `  strcpy(str,tmp);
  return size-1;
}
else
  return -1;
  F9 G) S% h# F  }! q}
int String::Rs()
: ^8 l- n; ^3 z8 Z, J' ^{
char tmp[256],c;
7 V8 X& N0 ]3 [+ H& e int i=0;
2 ^. j4 F& ]$ m3 d& ^ while(in&gt;&gt;c)
{
  if(c!='*')
! N* s% k- B) V* |" L  tmp[i++]=c;
1 q3 l# U, d, ?! u  else if(c=='*'&amp;&amp;i&gt;0)
   break;
}
0 P# j" J8 Q: y6 ^ if(i&gt;0)
  u, u. @6 a3 F8 j4 u; [ {
2 |/ h1 R. V" v; v* @  delete [] str;
- P+ Y% R5 c5 o- x5 O  size=i+1;
+ P4 W% [7 }" x/ p  str=new char[size];
  if(str==0)
+ W& p  k% v. G# D5 H5 S   throw "error";
  for(i=0;i&lt;size-1;i++)
      str=tmp;  
6 n' ?  {8 ~/ I6 u) c- x  return size-1;
}
else
  I$ Y6 B( Y" f2 [- ?1 N8 O8 ~  return -1;
}
void String:refix()
7 o" T4 l( t& t+ x. t{
int m=Length();
9 T# Y9 B2 U/ i6 p; _ delete [] pre;
: f# C& j6 `- l- t( g/ w* y9 b pre=new int [m+1];
pre[1]=0;
int k=0;
( J% M* }' ^5 l" v* m for(int i=2;i&lt;=m;i++)
  L+ ~9 M; l: ]2 i1 U {
# |. o  `5 H% ?* f  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
   k=pre[k];
7 T9 q$ Y# ~& N+ \$ k         if(*(str+i-1)==*(str+k))
$ s+ j2 c! {$ j' B    pre=++k;
7 N# E- @) N3 Q5 {   else
    pre=0;
}
% x, @' q. C! A/ ^7 e; q# i( m7 ^" t}
void String::ModifiedPrefix()
+ r- v. J% J; Z( h' h% Q- K{
5 F4 d9 S& u" |4 _% O1 {" z int *f;
int m=Length();
f=new int[m+1];
Prefix();
for(int i=1;i&lt;=m;i++)
{
; S0 Q, M6 A0 [7 P# D    f=pre;
}
for(i=1;i&lt;m;i++)
! S+ l0 C. ]" |/ i; c {
+ M5 `6 |3 q6 P- s1 d" t  int k=f;
  if((k==0)||(*(str+i)!=*(str+k)))
   pre=k;
  else
( o( R3 q, D$ L/ P( T   pre=pre[k];
}
! }. s) x" c' R9 H5 y delete []f;
. N& I  H  q5 j, x* c}
1 c) P) X$ p6 N  m+ @" @int String::Match(int i,String&amp; t)
{
int j=0;
) u( `- Y" ~, F4 F/ g& U int n=Length(),m=t.Length();
t.ModifiedPrefix();
* W) H+ u# r& ^ while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
  {
3 s( K" e' U. u7 l6 i2 S   i++;
   j++;
  }
  else
   if(j==0)
% W, o; Q3 {+ T- ?$ w  a5 V( [        i++;
      else
; h; y6 {8 x/ Q3 H5 Z    j=t.pre[j];
  if(j&lt;m)
   return 0;
  else
( e2 V5 Y! w0 \7 N   return i-1;
. p3 T; Y6 x. B$ G+ H0 Z4 c}
, e. m9 N$ v* Kint main()
{
2 e6 p1 i0 J" ^6 o( f6 s if(in.fail())
{
2 J2 Z; s6 {& W4 B7 B( b1 p  p  cout&lt;&lt;"the input.txt is not exist!";
' L+ _( a: X* c% V  exit(1);}
int i=1;
; v2 n" @- c9 j- ?8 \+ n String s,t;
s.ReadString();
while(t.Rs()+1)
{
0 P' q! `7 D5 Z- ^. U5 ?$ @) M  i=s.Match(i,t);
4 T) [4 x2 }" P& z  if(!i)
  {
      out&lt;&lt;"No"&lt;&lt;endl;
   break;
  }
7 Q6 E5 c; ~* A! ?9 w) s3 f0 y }
+ c" S% D4 f0 e& [ if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
9 Q! V# j8 P: [. u( F+ C0 b return 0;
}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看