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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
1 o6 _9 d2 e  [, U0 R: A#include &lt;fstream&gt;
+ ]8 r/ H8 p) @using namespace std;
) e3 g& |0 x  G* F6 Cifstream in("input.txt");
% H; h2 x8 Y3 bofstream out("output.txt");
class String
{
, L" {! a6 Y1 M( c+ H) h, O9 i5 x  public:
String(char *s="");
String(const String&amp; s);
& M, T& Y" a0 @) C5 p0 ^ ~String();
0 `; N5 j; z  `& f6 B, R int Length() const;
7 V4 Q0 {5 x! ?* d int ReadString();
int Rs();
0 y5 o: G, A3 ^& D3 O" x& V void Prefix();
' _0 z5 W1 ^6 ?+ D6 G" O void ModifiedPrefix();
+ i, E) E4 l( t3 P! w( g int Match(int i,String&amp; t);
  private:
   char *str;
. d/ Q$ T& S$ E3 O( ]   int *pre;
5 C, D5 w" j' k$ l   int size;
' f9 ?) I9 x6 b};
9 Q5 |; ~' y1 _$ d) e. `) j' o9 E$ WString::String(char *s)
{
, {" g0 H  B4 ~/ L size=strlen(s)+1;
str=new char[size];
if(str==0)
  throw "error";
1 [4 W+ a- N) G( U0 _8 }+ l strcpy(str,s);
pre=new int[size];
if(pre==0)
( X  h! Q) C" [* y& `; u% r; X  throw "error";
}
2 m1 b$ R2 c7 z+ I0 X) G! k7 HString::String(const String&amp; s)
{
size=s.size;
% R! Z( G2 H& U/ i4 q( ?" Y str=new char [size];
5 `% R- D" }* I! s% W if(str==0)
  throw "error";
strcpy(str,s.str);
pre=new int [size];
if(pre==0)
  throw "error";
}
+ q' |/ K. ^+ vString::~String()
{
$ ~- t+ l8 N$ s( S* ]. V6 T delete [] str;
& ?  J7 @/ U# q$ O' f$ l( y; X+ O- L delete [] pre;
}
+ [1 Y0 O, I% R9 _  kint String:ength() const
{
+ Z( `6 S! r- W return size-1;
}
7 T+ z/ `; f! ]* Dint String::ReadString()
! |3 i% M* o9 ~% V{
- G' L% p, M# u char tmp[256];
4 D, M9 S: l1 G) k; {' i    if(in&gt;&gt;tmp)
{
0 i; |4 K( @5 ^7 }7 I2 W  delete [] str;
. o. {2 f* A: g+ P- Z$ c- @7 T  size=strlen(tmp)+1;
  str=new char [size];
  strcpy(str,tmp);
! \4 ?( O: u. F% V8 X  return size-1;
}
else
  return -1;
}
- F1 S9 t& I- j. }4 G. @( Fint String::Rs()
{
char tmp[256],c;
% {, q( `3 `, k3 {( A int i=0;
while(in&gt;&gt;c)
- ]4 Q0 Z& p! ]6 d$ d: }) c {
- v( B+ l' n8 H  if(c!='*')
9 K/ I2 V" _% _  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
   break;
}
  ^& t4 s1 A: B9 O; F' ~1 F0 `) @ if(i&gt;0)
. i0 `7 w3 |3 ~2 C' L5 _) V4 V  b {
  delete [] str;
  size=i+1;
# @% g4 V% G, G9 O# J4 J8 W# `- U  str=new char[size];
+ j1 |2 E2 `" E: }% T8 J8 W  if(str==0)
, E6 q" b5 i, S% i+ v9 k9 A   throw "error";
# a9 s/ J8 m/ p5 T9 S8 f  for(i=0;i&lt;size-1;i++)
      str=tmp;  
# l' c- R. y) N& k  return size-1;
}
else
, }7 G% X6 e9 D/ R  return -1;
$ n, c, y5 k) o& c' G# H}
. X. l) }; ~) \8 N% Z2 ?! Ovoid String:refix()
{
. K. H% v% E. x6 H# c, X( g int m=Length();
8 ?" j$ l2 b4 _* m delete [] pre;
pre=new int [m+1];
pre[1]=0;
int k=0;
+ B  N( w0 r  Y4 T+ g8 e: F6 \ for(int i=2;i&lt;=m;i++)
; C3 `+ B3 C' Q+ | {
5 Q, k' Q; X3 J  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
- x2 O$ G- ?! c0 \   k=pre[k];
: _: l) f  }6 S         if(*(str+i-1)==*(str+k))
    pre=++k;
   else
( O4 d% f' O3 s1 z    pre=0;
* q9 R4 d+ m: c& H. G8 d+ T }
5 R) X1 K2 e4 R2 P}
void String::ModifiedPrefix()
: ]; s2 A$ y$ i, D{
int *f;
2 F/ g( L; Y2 q6 v int m=Length();
7 p) t6 Y& ^( H! q! o% P0 H0 s1 | f=new int[m+1];
Prefix();
5 T* h; K, N  I6 q8 v for(int i=1;i&lt;=m;i++)
* _# u! i: W' \, J6 R4 P {
    f=pre;
; Y+ C8 W6 r; F  y) j: B% m0 u }
for(i=1;i&lt;m;i++)
; \& L* A3 R$ Z, ~5 e# e3 J {
  int k=f;
; l" U( n  Q8 J: `  F( \, z+ a  if((k==0)||(*(str+i)!=*(str+k)))
" \" a2 m; K, k+ z/ M   pre=k;
  S# ^/ S; L; T1 C, B  else
$ L: Z# c  n* d2 q7 x( @( D  C   pre=pre[k];
& f5 p9 X, s4 ^2 \ }
0 w' m* z) L& g delete []f;
}
3 E0 t# I  p/ r: g% M5 Fint String::Match(int i,String&amp; t)
- B" ]. T2 C& s1 Q' V% D+ [2 |{
int j=0;
int n=Length(),m=t.Length();
7 I  l5 u) S( J7 c0 l, Y; S t.ModifiedPrefix();
" C; F; S2 A& H+ \: y5 `, s while((i&lt;=n)&amp;&amp;(j&lt;m))
- d0 a/ B; l& a- L6 @. W$ l4 d2 o  if(str[i-1]==t.str[j])
2 W. ?9 B0 S) q4 i. ]6 H' a  {
0 u5 s/ x" \. ^; i8 s, z3 o   i++;
2 ]% G5 S7 T( S  J; W3 u8 F' l) A   j++;
. e% N# q7 ^. M$ P/ F5 z% }$ C  }
. i+ K  x) F; d7 m  W& \  else
1 C  N& h. q! _. O3 \+ X' z   if(j==0)
        i++;
+ T" O0 K- k9 W4 v7 s      else
    j=t.pre[j];
: |* k5 a+ H4 z0 `  if(j&lt;m)
   return 0;
  else
   return i-1;
}
9 \* T$ b( E  Q3 Zint main()
{
0 R3 |: V/ b# h) @( T- e% h if(in.fail())
3 c+ s/ Z3 Y2 x8 J, I {
  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
int i=1;
+ _; k* k* |/ l% P) O/ s3 j String s,t;
6 w6 p1 J& L, c, D s.ReadString();
# B0 c: }1 L8 z5 c& d while(t.Rs()+1)
, p  k! s( F9 k8 B9 H# a {
5 L0 c; Y* E/ x6 ^  i=s.Match(i,t);
  if(!i)
7 W3 ?1 U3 U+ x$ O; Z  {
      out&lt;&lt;"No"&lt;&lt;endl;
   break;
  }
6 D5 e8 H# M+ y! L }
4 |6 Z9 k- G! I; t& p if(i)
# O2 k7 e: ?, h1 J/ N' P  out&lt;&lt;"Yes"&lt;&lt;endl;
return 0;
/ F  [9 p" `+ J  f1 B}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看