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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
* Z: C& v, [; C0 c3 P& ^' N/ fusing namespace std;
7 e- d2 M/ g) H2 i1 Vifstream in("input.txt");
ofstream out("output.txt");
class String
! Q9 h8 ]5 a; `% K8 C/ ]1 W{
5 ~! E/ R% L  `+ t# B1 ^  public:
3 C3 M% u& N6 L String(char *s="");
, H8 f) r8 Y+ h; I String(const String&amp; s);
~String();
# t4 G0 W6 G/ n: d7 V0 n int Length() const;
int ReadString();
int Rs();
void Prefix();
! W& ]; F* E3 P7 A1 \ void ModifiedPrefix();
0 _' p2 A5 I5 j% a# Y0 \9 u int Match(int i,String&amp; t);
+ w+ }, L" J" C) H$ L  private:
+ [* [* f0 H! f+ }- Z# R   char *str;
) w5 _" p& B+ h  |' s   int *pre;
- n% A4 x) B5 L4 r0 R7 s5 H   int size;
};
String::String(char *s)
{
size=strlen(s)+1;
2 a# m! J0 ~. b str=new char[size];
if(str==0)
% b$ b5 l( @6 |7 C9 _, h; @. P  throw "error";
; {4 }% F8 L/ V& p! M3 P& B strcpy(str,s);
! R/ G5 _# F2 D pre=new int[size];
& H8 v, Q8 q3 I( P( \ if(pre==0)
, B( s# f/ g5 }5 i) q$ c2 |  throw "error";
( e) n+ [0 H9 V6 s# i/ y}
String::String(const String&amp; s)
1 F4 Q6 X/ b* A& _$ y{
4 d4 @7 I8 Q, A6 O size=s.size;
! h1 \8 f3 A5 x  a% S# M4 F9 r& J str=new char [size];
( O4 n( D1 X/ L& K+ X  d( O4 ^ if(str==0)
  throw "error";
5 r4 d3 O4 ^! `3 U0 m strcpy(str,s.str);
& @. n6 M0 v( [: @& a pre=new int [size];
. Y  t  }. _" _ if(pre==0)
  throw "error";
  S1 n  A( h! u/ R8 R# {8 p! d" ^}
7 c, }& m; u# u0 M# o% _- PString::~String()
1 _9 s5 W) \; [, M6 R0 {{
delete [] str;
delete [] pre;
& d+ {* T1 w3 o3 t" `0 |) O( q, _}
int String:ength() const
{
return size-1;
1 f6 S) h: T5 n" O}
int String::ReadString()
  W/ k6 S7 W: F8 m{
char tmp[256];
! s) H, l/ \; a( \# S5 {! \0 o    if(in&gt;&gt;tmp)
. }: i7 _+ h% v2 g9 \  q {
+ F; j! U8 f) l) ?6 h  delete [] str;
0 c7 c/ w8 I: Z/ o2 @  size=strlen(tmp)+1;
  str=new char [size];
' J& o8 W7 f% ~  strcpy(str,tmp);
, i- C  d. y5 t2 H  return size-1;
}
9 f- W. K. N& f/ j) | else
" Z- f$ ~' F# d5 |  return -1;
}
int String::Rs()
{
char tmp[256],c;
int i=0;
- z9 H7 [* Z8 _9 q/ C while(in&gt;&gt;c)
{
& z3 }/ e: ]0 R* q  if(c!='*')
  tmp[i++]=c;
9 a& n8 l- n2 u5 g, o  else if(c=='*'&amp;&amp;i&gt;0)
  I0 q- y) j* \( C' j   break;
& d$ U# ~2 T, @" @ }
, n7 n& Z" B1 {) r: ]. @ if(i&gt;0)
{
  delete [] str;
  size=i+1;
  str=new char[size];
, f' S/ {/ G4 I* L: ^  if(str==0)
   throw "error";
! V+ E( e/ V& \" F' q. r! u  v  for(i=0;i&lt;size-1;i++)
+ e/ A% k: w0 O9 h5 D' u& z      str=tmp;  
  return size-1;
) _" u' T' ]" f* R0 b! V0 T! h3 \ }
$ t$ ^' ]5 T! F8 w' M# `! ~6 }/ B. A else
  return -1;
  \& M) \2 s( A' b}
5 F$ n/ _& T: C3 V; M% T, p" Hvoid String:refix()
{
  [1 o" O2 U$ A: c3 n: w int m=Length();
delete [] pre;
pre=new int [m+1];
8 Y, l2 w0 m& c/ I2 r4 |7 n; k+ w pre[1]=0;
int k=0;
for(int i=2;i&lt;=m;i++)
' s! I3 f0 ?, B3 v( o% H* E {
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
* ]" d& S, d  @- a9 D   k=pre[k];
         if(*(str+i-1)==*(str+k))
    pre=++k;
   else
9 S4 i: X; {2 \# w# n. d$ \    pre=0;
}
}
void String::ModifiedPrefix()
{
# O5 }0 a/ l. X4 I: s- i; b int *f;
% r8 u- Q$ F& ]7 E int m=Length();
f=new int[m+1];
2 k3 f" s2 A5 h) R Prefix();
for(int i=1;i&lt;=m;i++)
{
    f=pre;
}
1 ~  ?0 U7 E2 `! U  W9 Y for(i=1;i&lt;m;i++)
9 ?5 w, o8 w4 [9 c4 N/ T; c {
5 L  Z# p* H" q; Y, F  int k=f;
; k8 F+ e: o4 y3 q  if((k==0)||(*(str+i)!=*(str+k)))
9 @1 d& I. J4 C+ h) k   pre=k;
9 w9 n/ j1 `2 t) h  else
   pre=pre[k];
}
0 B+ o7 P- h# D4 X: z% i! v delete []f;
  e/ ]: {. F" h* s7 b, i" @}
1 C! ^" d" N8 [+ `' C7 ^) ], }int String::Match(int i,String&amp; t)
; _+ B& Z& g, A" w$ B! M{
. Z# t8 J7 |9 R) X1 R" t int j=0;
) {/ G% y) }9 u5 g. {' ] int n=Length(),m=t.Length();
; u8 m  i, \( O  B% h8 z$ N t.ModifiedPrefix();
3 r. I: K7 F6 A6 k8 b while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
  {
   i++;
   j++;
6 G; {. k+ a7 m* {0 C4 ^7 C  }
7 Y! S; ^- d; M9 M! Q* ^: u  else
3 \4 z) U  J7 c4 }   if(j==0)
        i++;
      else
8 h) M( O1 a% M- _5 m( P    j=t.pre[j];
  if(j&lt;m)
   return 0;
: n% L, H1 P8 L  else
( Y4 W8 Y9 Y4 x$ ]" j   return i-1;
9 }7 N' ~1 ~, I/ U- \4 ^* W& }}
int main()
% d# N, v8 H& ?0 k{
if(in.fail())
$ O0 T2 E! J8 C$ g5 m9 l {
; u8 f: D: F; u* J+ Q& U) G* i  cout&lt;&lt;"the input.txt is not exist!";
' p6 h6 k% K0 m  exit(1);}
7 E+ K1 n7 k" z* o: v6 P int i=1;
8 S) y# P' H. }" ^4 \ String s,t;
3 k" g  N* w& E! l s.ReadString();
0 H# d4 C" R- _6 |! c# n while(t.Rs()+1)
9 R/ j  `' x9 ?4 e1 w/ x {
  i=s.Match(i,t);
  if(!i)
" O* c4 S: r8 J6 F  J  {
. w" Y3 y! ]2 v0 t5 Y. g      out&lt;&lt;"No"&lt;&lt;endl;
   break;
  }
0 G# y" V" B0 \3 U: i, M0 R* k }
: i+ z# Z  ^/ ? if(i)
: C; a+ s  `% R% Z  out&lt;&lt;"Yes"&lt;&lt;endl;
0 ~+ w5 k+ e% u" D0 I- p. ^ return 0;
. f" c/ u* k: P3 |( R}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看