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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
! F. O/ h# F6 g) l+ B- Z#include &lt;fstream&gt;
# g" z7 p, X* u. `% W, ~- B1 Susing namespace std;
0 t4 U1 [5 }$ Xifstream in("input.txt");
ofstream out("output.txt");
class String
{
  public:
String(char *s="");
! Y4 o+ D# F& K" S1 i6 S, ]' j1 [ String(const String&amp; s);
~String();
int Length() const;
int ReadString();
int Rs();
void Prefix();
void ModifiedPrefix();
% K7 D& `* W# n9 o. ~6 v/ {; b int Match(int i,String&amp; t);
  private:
7 i) h2 J( k4 B7 y9 D  F   char *str;
9 K% ~6 B# z2 W   int *pre;
8 L; J7 `! o, t( o9 J/ W   int size;
};
3 I2 K) i- l" m) QString::String(char *s)
{
0 y# A7 k9 p- @' K size=strlen(s)+1;
, }' z' b# M, V% R, g  w str=new char[size];
7 |6 T6 R) }, ]2 z1 S# ? if(str==0)
% j$ w$ u# I/ ^# x  throw "error";
! ], O: |* k- L strcpy(str,s);
) P( W/ E6 ?# A! ]; R pre=new int[size];
, O1 A, z1 d- M1 z- |: I- g9 O% v if(pre==0)
( u+ D. K( F8 K8 K  throw "error";
}
9 a& B% ~  ?3 \String::String(const String&amp; s)
{
size=s.size;
str=new char [size];
if(str==0)
  throw "error";
strcpy(str,s.str);
" S1 Z% E' X; t" y% X. V; Q8 Q pre=new int [size];
, o# n4 p+ a& @( B: F' e6 P3 l if(pre==0)
  throw "error";
" e( V! p$ Z) ]" I( q1 k}
String::~String()
{
delete [] str;
( T( H$ h# f1 N$ j5 r9 A. w delete [] pre;
}
. ]* z7 _% N( J! _% @  v7 Zint String:ength() const
{
return size-1;
& \* k% A/ v9 R+ ?) T& N7 i; [}
0 m2 w3 v$ B2 n* E" oint String::ReadString()
{
char tmp[256];
    if(in&gt;&gt;tmp)
1 p3 d' _5 T$ \& `0 ~( k6 K; H {
  delete [] str;
% |  W2 N: o: O0 l  size=strlen(tmp)+1;
  str=new char [size];
* m1 w2 T3 f6 Y$ b( d  strcpy(str,tmp);
' V% V% y( V/ r0 X3 k# x$ W  return size-1;
}
else
1 {, d) ?6 }) u0 ^  return -1;
" B+ a5 J7 G; ^' h& O' a8 W}
8 y# A2 T2 T2 o" i4 v& M" `int String::Rs()
{
  w& J, N2 m7 @$ j char tmp[256],c;
! \9 o% Y# r4 v, x. j0 t int i=0;
while(in&gt;&gt;c)
{
9 N! b7 ?& w# |7 |! z  if(c!='*')
' v( W5 ]+ r% k1 W8 h7 r# ~* g  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
; N; m& y2 K8 l   break;
}
. O0 f3 N5 k& S) G if(i&gt;0)
: w' o6 F1 \" J  s9 E# e {
  delete [] str;
. F$ s' V$ d( r9 p1 W* y& u1 u+ v  size=i+1;
. Q/ {6 \- O" Y# ]5 q$ a  str=new char[size];
5 a4 r& g1 g, F, O( G, d  if(str==0)
   throw "error";
# V, P+ ^; ?) i1 N  for(i=0;i&lt;size-1;i++)
      str=tmp;  
& z8 Z; s3 {7 c, D  return size-1;
5 ^3 M& z! o. G' A- y3 c }
& s, G, b* \7 L/ F7 d4 a3 m1 u# t else
  return -1;
}
void String:refix()
{
; ], j  o7 c4 r. n3 S4 K: d int m=Length();
delete [] pre;
pre=new int [m+1];
pre[1]=0;
+ ^& Q5 Q3 M# C# z  y int k=0;
for(int i=2;i&lt;=m;i++)
4 z- C4 ~5 q# O% m {
9 a- u3 ?1 @. m: h) s7 G  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
$ \0 R8 ^" {" I5 A   k=pre[k];
. _# H$ V! J9 @4 f/ T7 W5 d         if(*(str+i-1)==*(str+k))
- S+ X1 E: k2 B* a/ k    pre=++k;
   else
1 V4 w+ t" l" h- K2 e. k' K6 ?4 m    pre=0;
}
}
* E6 d# j( A6 }. uvoid String::ModifiedPrefix()
8 }( g$ _0 S+ }! X* x2 L{
, ]6 Q' D4 |& C6 y' V- g int *f;
' c2 S# _3 ^8 r% a int m=Length();
$ [$ H( p. J6 \0 x9 J" W f=new int[m+1];
# s$ [7 U  ^0 }0 v% z5 @ Prefix();
for(int i=1;i&lt;=m;i++)
/ z* m/ U! o' V; Z& C) K) A {
    f=pre;
}
for(i=1;i&lt;m;i++)
+ a, q3 A# {3 _. {& P( Q, q {
; F% j- m" E3 D5 ^. r: k: ~( f  int k=f;
  if((k==0)||(*(str+i)!=*(str+k)))
   pre=k;
  else
   pre=pre[k];
}
delete []f;
}
int String::Match(int i,String&amp; t)
{
- d! B" |* Q" x int j=0;
6 r5 {  m7 g: l: _ int n=Length(),m=t.Length();
t.ModifiedPrefix();
$ Y& z3 m  k, m while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
  {
   i++;
" F  S, m3 a+ @& o   j++;
  }
  else
$ P, ^" _0 b; a) D6 {) @  \   if(j==0)
, ^: w' t6 Y( {' H* {, a        i++;
& ~: b* ^( d# i& B' o" \      else
    j=t.pre[j];
9 y5 m; x; D7 M5 r/ g+ @2 X  if(j&lt;m)
  b; B. N' Z4 X# B2 ]* B- M   return 0;
  else
   return i-1;
6 G1 ~; l/ B: z" `; J}
int main()
, O9 b& P1 P% V# F( ^- Z/ Z8 o{
0 N0 {% y# v. x if(in.fail())
{
7 T- S* ?" k1 a; Q( O; V  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
int i=1;
String s,t;
/ Z" u# B" v' `9 N4 E; U- K1 \ s.ReadString();
  v+ W4 R2 ^6 D$ f, K( u while(t.Rs()+1)
{
: a( T% E! y% ?! G, `) B0 h  i=s.Match(i,t);
  if(!i)
  {
      out&lt;&lt;"No"&lt;&lt;endl;
* B7 d( Q' }' m6 I   break;
  }
}
if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
return 0;
}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看