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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
1 k+ W7 R% t8 _$ V9 i4 y! l#include &lt;fstream&gt;
$ s# K1 T8 a) h. fusing namespace std;
' D: U) O0 C9 i/ J  qifstream in("input.txt");
ofstream out("output.txt");
) }% j! [  i5 i4 D  A$ C# d5 D+ Hclass String
# h' F1 e3 w# S  ?' ^1 L+ O{
  public:
: _5 C& _1 g% I$ G3 i6 H) J5 ~# l String(char *s="");
: C- E' U3 }, P' h String(const String&amp; s);
~String();
) m0 _% J4 v# ~' L8 A& B$ Y int Length() const;
) v+ d: V, c) v+ O& E9 K* b int ReadString();
int Rs();
2 ^+ F& n8 A6 r6 |7 b) I- h void Prefix();
void ModifiedPrefix();
int Match(int i,String&amp; t);
4 q0 h7 m$ `1 q, X/ A  private:
0 l( h4 d7 Q8 Q0 l% Q8 t1 \  r# y   char *str;
6 L- i# q' ~2 n- ?3 b0 n( @   int *pre;
5 `/ d- w4 w& j/ U: \' p   int size;
7 y4 ~' ]5 u8 B/ @) i};
- T' Y4 s9 F) L! k! WString::String(char *s)
& h. U* l; j% t/ I2 ]{
size=strlen(s)+1;
str=new char[size];
+ b3 D% b( S' w) Y) [1 x if(str==0)
  throw "error";
strcpy(str,s);
pre=new int[size];
if(pre==0)
6 [( I" L7 O- ~" ]6 P6 E  throw "error";
& n& N! W! d# P& @# N}
: L3 u# F; x6 x. R: dString::String(const String&amp; s)
{
size=s.size;
str=new char [size];
% A  U: x! I* F+ c if(str==0)
  throw "error";
strcpy(str,s.str);
pre=new int [size];
: C8 z& j. U4 d6 k# f if(pre==0)
  throw "error";
}
String::~String()
1 l2 @: Z) C$ ^4 x# }$ ?{
delete [] str;
delete [] pre;
1 G* I% e; ]$ M+ r+ g7 G}
- t* i3 o+ Y' h7 ~int String:ength() const
: J/ i! p5 k8 Y  a, M& d7 {+ U{
return size-1;
3 g1 m+ N# r! A7 ~* f}
* g* T7 i0 Q6 K3 v# H+ |6 }int String::ReadString()
, T/ p6 E- Y% ~- v6 |{
char tmp[256];
    if(in&gt;&gt;tmp)
% ?1 c' R$ X6 Q {
4 y/ b2 v0 u1 c: d9 H4 `9 g  delete [] str;
/ ?/ J. |/ i9 a  size=strlen(tmp)+1;
  str=new char [size];
2 A3 e  x3 E. Z0 k/ A- a' p  strcpy(str,tmp);
  return size-1;
& j9 W: I! t* \. N  D: _ }
2 x7 l# E! h0 ~4 Z% _ else
/ u* W, _. ^6 ~0 V  return -1;
}
9 A& `" T* p) p' Y; e, eint String::Rs()
{
char tmp[256],c;
int i=0;
4 \8 c+ o" b2 x" h# R, y while(in&gt;&gt;c)
{
  if(c!='*')
* y0 `* W  p0 K) ?- {$ e  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
& `8 x: H/ ~0 C# x1 p  d5 Z   break;
}
if(i&gt;0)
{
' i% q' f5 T# t5 K! I2 p  delete [] str;
$ E1 e. R0 k7 y6 k  size=i+1;
- H# B  w# w# k: N" _  str=new char[size];
  if(str==0)
   throw "error";
  for(i=0;i&lt;size-1;i++)
      str=tmp;  
- a9 F: @2 c' d. {  return size-1;
}
. S3 n3 Y2 {$ \9 D  m* f/ ? else
9 x2 g8 o+ i& M  return -1;
: |/ J+ h4 l/ d1 q}
3 c! o& k- V8 j, W" M5 M* Pvoid String:refix()
  f0 N/ t# v3 R" D; i! X1 O{
int m=Length();
* b; O7 y7 q0 q' w delete [] pre;
  k5 l8 b- p4 A) c# V0 R9 u; ~ pre=new int [m+1];
pre[1]=0;
$ Y/ S+ Q9 F$ D' E  T! q6 N: G int k=0;
2 X0 a4 M  e' {; X! C for(int i=2;i&lt;=m;i++)
5 N5 y: n. ?2 v4 C% t {
  g. @$ Y: Q2 v4 @- s: f" [  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
   k=pre[k];
9 t3 f1 H6 a0 w* k) X         if(*(str+i-1)==*(str+k))
    pre=++k;
   else
4 N" H8 ?$ W8 z" W    pre=0;
}
}
void String::ModifiedPrefix()
; _- F; g, s' [$ A4 M% f  T; @+ D% f{
int *f;
, |9 d- W2 s% B/ v  e! @( J int m=Length();
f=new int[m+1];
0 e. }9 i# k) t6 I- g2 H Prefix();
for(int i=1;i&lt;=m;i++)
4 x  [: ]( |5 t8 j {
    f=pre;
}
for(i=1;i&lt;m;i++)
{
+ {  V6 C: [6 c  J# E( ~  int k=f;
6 X" F. z+ X4 H* X! P  if((k==0)||(*(str+i)!=*(str+k)))
+ v6 a8 a/ j+ d: A5 y   pre=k;
" r) s7 ~6 T' V! f* P  else
   pre=pre[k];
}
9 J; r9 K3 l9 j6 j+ Z( N+ J/ v) U delete []f;
}
' ^* n; d2 ~3 T' b  K$ uint String::Match(int i,String&amp; t)
{
int j=0;
7 S6 R. B, N! f  p8 i, \# A int n=Length(),m=t.Length();
t.ModifiedPrefix();
while((i&lt;=n)&amp;&amp;(j&lt;m))
8 c1 g5 h" S0 b" ]  if(str[i-1]==t.str[j])
  {
   i++;
   j++;
  }
  else
2 z/ {  A, [3 U& v0 K, v3 X& Q   if(j==0)
        i++;
      else
    j=t.pre[j];
  if(j&lt;m)
   return 0;
! P( i- _' m' s  ^  else
   return i-1;
) t+ Y: x+ a9 m; Y: |! x# P}
int main()
5 e- `0 P. F9 Y; ?/ F3 Q, Z5 I# N{
if(in.fail())
  b: K/ ]: u5 w" s+ {; `7 { {
3 d, ~6 Y5 I" ]! w9 O% m9 g: b; ?6 E2 M; X  cout&lt;&lt;"the input.txt is not exist!";
% j' K' |1 q* w& T3 i  exit(1);}
9 T3 H" B9 Q9 O. }) L, K# g6 G) S int i=1;
$ U! ?: u  F; ?6 N3 w* Q String s,t;
s.ReadString();
2 c4 @) g- J. ]8 h- x# } while(t.Rs()+1)
0 P7 ^% p1 y8 h4 `; Z( J2 V {
  i=s.Match(i,t);
  if(!i)
  {
6 Z) Y: N3 `1 `6 @. h6 ~      out&lt;&lt;"No"&lt;&lt;endl;
( J6 i* V1 P% T- O( H   break;
  g) u% n8 k$ w: B  O& }  }
: U/ s+ U- B4 ?- S }
if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
( l0 e5 m2 S! d  M$ y return 0;
$ f( x( q5 L2 t. o}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看