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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
  A7 o0 z; t! D7 b+ q#include &lt;fstream&gt;
% c8 k  m. h( U: iusing namespace std;
" w, X0 n8 g5 F2 |: d9 V/ Gifstream in("input.txt");
ofstream out("output.txt");
class String
{
  public:
- y7 |5 @$ d$ [6 s  P% R* b" ? String(char *s="");
String(const String&amp; s);
2 }" u+ [$ |. Y+ Y% o& w4 X  X ~String();
1 c* N( k7 V- v  m" I" Q% v% l int Length() const;
: \. F' O" g; h, o: j int ReadString();
8 H& b4 \- k$ R9 O: E+ I int Rs();
void Prefix();
0 n" b, s- c5 U( C8 s5 E: @. f void ModifiedPrefix();
; h: Z9 w) z* M int Match(int i,String&amp; t);
  private:
2 J" W2 k/ L5 M" H! F, K: x' x# E6 s   char *str;
   int *pre;
   int size;
8 ^$ N  `' Q2 \+ g. v};
' M1 S, Z2 K; r# g! r0 WString::String(char *s)
{
size=strlen(s)+1;
str=new char[size];
9 u/ h, I0 {3 J) D* J& L' i- z; A if(str==0)
  throw "error";
" D- u' S% U0 j3 a4 z3 M4 N strcpy(str,s);
pre=new int[size];
( s9 P( J/ P* R* ~+ E0 ] if(pre==0)
  throw "error";
}
String::String(const String&amp; s)
$ G, N* @/ d3 N1 E{
% L. }1 [( y5 X' s  Z3 [ size=s.size;
% N/ F$ P5 Q$ ]" e4 y str=new char [size];
% B  q6 j& j; H" i* a' V3 ^ if(str==0)
  throw "error";
6 Q; U4 f7 A9 h5 r" l strcpy(str,s.str);
pre=new int [size];
/ t0 H2 O  X4 w if(pre==0)
  throw "error";
}
) y1 }1 m$ B7 Q) bString::~String()
{
delete [] str;
# |" \( x0 _  O8 D delete [] pre;
6 @1 R9 w9 v( U7 [1 y+ U, i}
4 ?' N" s+ I8 L0 w; Zint String:ength() const
{
8 q  j$ l$ k3 x' m2 A& y0 ] return size-1;
}
int String::ReadString()
{
char tmp[256];
6 i9 |/ X- D9 b  f& i    if(in&gt;&gt;tmp)
{
  delete [] str;
/ V) j. Z# \% e" h; M/ r6 l  K  size=strlen(tmp)+1;
  str=new char [size];
( m2 A# r: M  E8 T  K  strcpy(str,tmp);
  return size-1;
}
) }' d; n( [& R- t else
( I6 ^9 n1 n! v" N  return -1;
}
int String::Rs()
{
char tmp[256],c;
) s3 r* S5 w* z7 c! u: d* A: Z int i=0;
while(in&gt;&gt;c)
) X4 {9 ]0 A  \; t/ q% ], n {
' T+ j4 _  |  t: `2 F) E  if(c!='*')
1 B# ]$ g% O9 B0 H* G  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
$ P4 q1 l) J( m! {4 ]9 g& E   break;
}
- z. c! M/ u3 q1 X5 Z if(i&gt;0)
{
4 l$ D# `' c' V' |( ~. r5 z, j  delete [] str;
! w) \. P6 u/ C9 L  p  size=i+1;
5 h1 {. L* N! ]% G2 e6 E4 X1 Z  str=new char[size];
, F) T. y# `+ O5 n; @8 S  if(str==0)
   throw "error";
3 ^: D  t1 c( j$ O2 m0 R8 m  for(i=0;i&lt;size-1;i++)
$ z  i+ A" ]1 B. X5 _% M1 B* n      str=tmp;  
" x) n' ~/ t+ x% h7 N/ m+ C  return size-1;
}
else
  return -1;
) x6 D$ W" L5 T' r$ n8 p3 R}
8 u, }) Y0 z' G8 _! r! Evoid String:refix()
{
6 f; ^4 H2 x' r7 f( H6 \ int m=Length();
delete [] pre;
7 {4 V6 x( K8 |% r  f2 h7 {0 W pre=new int [m+1];
1 o' d! Y( |' v) q  g pre[1]=0;
int k=0;
- n1 Y) b- Y/ s2 @# v for(int i=2;i&lt;=m;i++)
9 w" [. Q1 o) }, M4 C {
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
   k=pre[k];
8 C$ Z$ n$ o! U: {- U% R         if(*(str+i-1)==*(str+k))
3 A5 T1 [" H8 `" W    pre=++k;
   else
( @  P8 U4 ?% t3 L    pre=0;
" V2 r, _2 [* _( s9 T$ q: [ }
$ _4 j7 v$ g8 `}
void String::ModifiedPrefix()
: z3 p2 T- A1 {2 g; \% W- c{
1 X+ d! P, t8 `8 J) R1 x2 |# M" u int *f;
int m=Length();
% S- |4 Q4 g( ~$ L: e& l% ` f=new int[m+1];
' \  v" l. c6 @  P3 g Prefix();
for(int i=1;i&lt;=m;i++)
{
7 p0 M' Y7 V  \    f=pre;
}
, K: f; L8 K! u$ Q* X+ u for(i=1;i&lt;m;i++)
$ o& m' G1 x+ g1 K {
; a: s. D8 M) M+ _" \+ A  int k=f;
: r3 \* W5 H& B, N  if((k==0)||(*(str+i)!=*(str+k)))
   pre=k;
- W) \# Y: p; Q0 |& r4 m- P  else
   pre=pre[k];
}
6 z' b7 R& L9 c+ M% V delete []f;
# t# H3 o/ b: Y9 ~- h( v  Y}
( o" P5 n' @" [" Y2 [" x* ^! Oint String::Match(int i,String&amp; t)
{
* S7 C# X8 }) k% K# h; Y2 { int j=0;
, e: O+ O$ w$ F- [' S; |4 w& C int n=Length(),m=t.Length();
t.ModifiedPrefix();
while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
  {
* F3 x5 l/ ]4 p5 ~" ~$ ]' A: @   i++;
   j++;
$ E' H0 h' Q1 m  }
; d! {$ J. W$ l, r9 ~  else
   if(j==0)
/ n5 W& t2 r2 B8 }        i++;
/ E( g6 r$ @9 \% s. p8 [" M      else
    j=t.pre[j];
  q; V4 ~4 y" \8 i% b4 ]  if(j&lt;m)
; z$ o+ N, I) E   return 0;
2 X% n+ V- b# U+ k7 p# n5 D  else
   return i-1;
}
, [4 ^, ?- N& Y0 i# s  i; K8 A0 O2 L" }int main()
3 ^& K  f* X. C{
if(in.fail())
- J( \3 x; R5 x {
  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
int i=1;
String s,t;
$ @, b1 u' _9 ?0 t5 X s.ReadString();
3 y5 G- M( Q, |, Y while(t.Rs()+1)
{
  i=s.Match(i,t);
  if(!i)
  {
      out&lt;&lt;"No"&lt;&lt;endl;
   break;
# q! ]  p: \+ |4 L/ k0 N7 w, k  }
8 b% d/ G- y' X8 A3 t }
if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
return 0;
}

ottiou

看看看看看看看看

zhaoyunfei1126

好吧[em03]

hyacinth13

<p>谢啦~~</p>

ari0101

谢谢

sgnswb

顶

zidance

看看啊