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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
using namespace std;
ifstream in("input.txt");
5 R, B! ]% _* Xofstream out("output.txt");
class String
{
  public:
# {" r/ y/ ?6 S7 t6 C String(char *s="");
String(const String&amp; s);
~String();
% ~, t% d7 s3 j6 ~7 x  ?- ^' E int Length() const;
int ReadString();
int Rs();
void Prefix();
void ModifiedPrefix();
+ _& v$ h9 V) K1 {2 W int Match(int i,String&amp; t);
  private:
   char *str;
. w/ m, [- F, \& e8 C0 `4 w/ S5 L   int *pre;
- b+ p+ Q) z! v   int size;
};
String::String(char *s)
{
6 v! _9 z; |, C size=strlen(s)+1;
str=new char[size];
if(str==0)
* j( L+ x' q0 K6 O  M  throw "error";
/ V7 `* n9 h) M1 c strcpy(str,s);
pre=new int[size];
: ]3 A$ |* |2 C5 j' C if(pre==0)
& s: n7 |) u6 Q$ N  throw "error";
: B2 ^/ w" Y1 P9 B1 t1 n7 f: i; V}
String::String(const String&amp; s)
! D; z  p& w$ V, j' g- C{
( k) [4 h. _; b* F8 W1 ~" ~; \. I size=s.size;
/ c9 S0 R. H2 O( ^9 b str=new char [size];
; i8 E* i2 l  _" @: @7 {% m if(str==0)
# `9 d  U" ~, o. ?! m2 ]7 {  throw "error";
strcpy(str,s.str);
pre=new int [size];
# v2 M+ L) ^1 n, Z3 I9 { if(pre==0)
$ A2 \# Q5 U% H; a) j7 g  throw "error";
}
8 S: f/ M& X. h& ~String::~String()
! H& b5 ~3 t2 I{
delete [] str;
% t* R% l. [& T* A delete [] pre;
& w$ C' t) F  j+ H; w}
6 X! [& B6 s, }# ]: S0 K/ m3 Cint String:ength() const
{
return size-1;
}
int String::ReadString()
$ q( R. q4 R3 u4 z0 \) Z/ j{
  n! J# C- S& b- P char tmp[256];
    if(in&gt;&gt;tmp)
{
' P, `- z4 a* q0 f  delete [] str;
/ W1 Y. h; |) C( c, p4 T- F9 O  size=strlen(tmp)+1;
- p/ p  ~+ X- K' J- Q2 [! ^  str=new char [size];
  strcpy(str,tmp);
' ~9 f& A0 ~, L# L  return size-1;
6 r0 M, E7 C# s, c( m, Y) N4 O# o9 J2 M }
7 K- h; j" T7 u4 a. ?$ W. N5 H else
  return -1;
9 [% f, {- I0 ?" l4 d}
' Z) r- K. X- a0 g) h9 Nint String::Rs()
{
char tmp[256],c;
( ?' L( s, k7 Q int i=0;
- {8 v- k7 X! y& y+ }/ T& } while(in&gt;&gt;c)
3 \/ k4 P2 L9 p {
  if(c!='*')
  tmp[i++]=c;
# S4 y3 i! X. S3 |5 R4 b  else if(c=='*'&amp;&amp;i&gt;0)
8 R' R# b0 S9 v! H, H# _7 N$ Q   break;
}
# g& A+ j# w$ w+ G# y- o3 G if(i&gt;0)
, h" Y: X  v( e. t1 s& f* J {
! U/ H- l1 r! H  delete [] str;
  size=i+1;
  str=new char[size];
  if(str==0)
   throw "error";
  for(i=0;i&lt;size-1;i++)
      str=tmp;  
+ Q6 j$ P( q* b. q: D  return size-1;
}
1 }8 M5 R. ?7 `8 r; V else
2 ]+ x6 F& z2 ?7 P  return -1;
}
void String:refix()
{
int m=Length();
% K, W' [/ {- |  t. M$ n delete [] pre;
. y& m  C3 t4 _- G6 F pre=new int [m+1];
, T5 b4 o/ e, k/ R pre[1]=0;
2 o, r3 s% V& ]7 t5 q int k=0;
/ ?( k1 r9 i& Z* L  V for(int i=2;i&lt;=m;i++)
{
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
; w& N' l$ }2 u8 _% m   k=pre[k];
         if(*(str+i-1)==*(str+k))
    pre=++k;
   else
    pre=0;
}
}
void String::ModifiedPrefix()
7 A  E9 Y2 T; z9 |{
int *f;
int m=Length();
% y* q$ Z2 S  }4 X- t f=new int[m+1];
6 k7 L  M3 K  s. a$ k Prefix();
for(int i=1;i&lt;=m;i++)
1 f% ?8 E: `) U {
% ^: E  W% r$ y" I    f=pre;
}
' p1 `4 O9 o- H for(i=1;i&lt;m;i++)
{
% M8 Q9 h& t' l- g" m- V; A  int k=f;
" z' a4 ~0 I$ y  e* [  if((k==0)||(*(str+i)!=*(str+k)))
   pre=k;
  else
0 ~8 X7 S( ]* p$ [' V7 y, y   pre=pre[k];
}
$ D3 q4 o- l& Q  \2 P0 G, p delete []f;
}
- m  g$ `% m# `( m7 W  w' Nint String::Match(int i,String&amp; t)
{
) v# k8 b4 }# d, u8 r  f int j=0;
int n=Length(),m=t.Length();
t.ModifiedPrefix();
while((i&lt;=n)&amp;&amp;(j&lt;m))
. I. e& q2 Z3 n. A  if(str[i-1]==t.str[j])
  {
   i++;
* x' x) M2 _% e- ^  S! Q1 O   j++;
5 @! F* e# |8 N. O  }
  else
+ x) _3 K! }- n/ {& g3 M9 n9 F   if(j==0)
        i++;
      else
    j=t.pre[j];
* }8 w$ X! _! h& ^- \. u  B  @2 B  if(j&lt;m)
) e, y9 Z- A: I( i. H+ `( r1 s* H, _1 p   return 0;
+ V6 b- Y% W5 E% d8 X+ j# C  else
8 ~" @1 Y3 v! Q: b: P0 E$ m   return i-1;
, Q+ u% }" {& ?" _; b, U/ w& z}
4 t  y$ m4 F5 J7 e/ J' pint main()
, h* O+ H/ Z( A* s$ c6 z& h/ B. O{
1 s! ]  S. ^1 d: R/ X if(in.fail())
; Y6 e4 _& T3 n1 ^/ [3 o3 e# h {
  cout&lt;&lt;"the input.txt is not exist!";
; b. N/ a4 L; `6 r) p! E4 ?  exit(1);}
% Y2 w; V- K6 g" A) h$ o1 I8 p int i=1;
String s,t;
$ P/ l/ ^: K# e/ G6 c8 ]  d( P8 D* x s.ReadString();
while(t.Rs()+1)
* v6 V2 |2 j% v! i. t {
1 Z: I. m- d! [2 `  i=s.Match(i,t);
- z( ~0 K& m7 M+ U& d  if(!i)
& l# ^7 D) h* g; ^# n/ H  R  {
      out&lt;&lt;"No"&lt;&lt;endl;
+ r! E; w) N7 g; m+ P* }   break;
6 u/ Q% r' [; x+ `# Y  }
}
& U5 U' Z' ?. H; r if(i)
; S& s! l: [  ~& c+ u  out&lt;&lt;"Yes"&lt;&lt;endl;
return 0;
# a5 R/ h3 }4 X* f8 P1 P- U- Z}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看