数学建模社区-数学中国

标题: 间隙字符串匹配问题（c++) [打印本页]
作者: lynnyan    时间: 2005-4-22 01:37
标题: 间隙字符串匹配问题（c++)
<>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>
: \: O' L- @4 o1 }<>[[/hide]</P>[attach]1460[/attach]#include &lt;iostream&gt;1 d8 R$ \/ H, N- D) ]
#include &lt;fstream&gt;
6 I" E& |$ L! Pusing namespace std;8 s* j( ]0 M- n- `1 o6 {; n" u5 o6 E
ifstream in("input.txt");
6 `5 F9 _: a3 x; k5 r2 ?ofstream out("output.txt");
2 E3 e! l( [4 tclass String
- |/ K/ [; Z1 r2 N$ F{2 {3 \& m4 d  n/ e1 R/ P
  public:' L7 L9 C' n/ Z! _
String(char *s="");$ _+ T# B' l8 w  t8 l' S
String(const String&amp; s);
7 O9 j- B* r/ ]8 N5 ^ ~String();/ O4 g2 H/ b4 s; [4 M
int Length() const;6 W+ @1 ~! }+ R0 y" E5 ^0 V
int ReadString();9 m+ d. Z. R& Z9 C
int Rs();1 [; u/ q. O; l. g
void Prefix();
; G- E7 X  t) S* T' ~ void ModifiedPrefix();5 s8 C7 Q; k# h! T' B  g7 O
int Match(int i,String&amp; t);
$ i- t! D" A6 H4 ]. B  private:
$ k) a* \; q! ]4 {   char *str;8 A# n4 t: E2 V1 n2 x4 _
   int *pre;
! L  L' r4 }9 H6 j( ?7 e: ?; j+ m   int size;# |8 [1 [4 n5 Z3 m- [# E
};
( }( C; {9 Q6 pString::String(char *s)
9 v4 F  a+ }2 g  j{
4 X5 y# I7 ?: O, _4 {- C$ `8 @ size=strlen(s)+1;6 N6 G  X% _: v2 F8 C3 O3 O1 a! v% Y
str=new char[size];
6 o% k( B5 t9 K; Q( ~3 L& C if(str==0)
2 x! {1 ?) E2 E* G& h. p2 }  throw "error";
2 _6 I3 h# f. [! p2 {  j  F) B: q strcpy(str,s);
! P) M. U: J0 x pre=new int[size];( s& i% @* w8 T8 q
if(pre==0)6 {; o% b$ ^$ [+ m4 }! L& Y) a
  throw "error";
9 @' Q! p% X" e- D9 Y0 Y% G}* G# p7 w# M# s( Y) O
String::String(const String&amp; s)
( B) V9 S% J  W3 ]{) k9 {$ N+ l" \- N7 X
size=s.size;1 v9 I" |$ B( a1 c- ?
str=new char [size];
& {' _4 T4 u( x6 s/ _  p9 D/ K, c6 J if(str==0)
. Q: ]& F* R! |# k/ \. S  a# {  a  throw "error";8 E9 z6 f4 m5 v  J5 i3 [
strcpy(str,s.str);/ Y1 `9 ?/ T# E. g2 V6 Y
pre=new int [size];0 _2 J# K  i) V/ z
if(pre==0)8 g7 B+ _$ ]' I: [0 v: \  Q3 M% }
  throw "error";" i1 Q6 p+ S& M& w; w0 r! ?
}
8 j% q0 Z. B$ m1 s  Z4 s( IString::~String()( y8 k) R2 J* }; G: x
{
( K  F5 W" A/ w5 z) M3 p# M delete [] str;
+ O: ^% k! L- n9 H% c) J# v% t delete [] pre;
2 `/ d: ]- q+ k$ R}
2 w  M/ u, B* G; |; Kint String:ength() const
- H+ J0 [4 M$ ~1 p{
! g1 C. I! N! L! m& B; g0 i return size-1;& Q- w9 C9 y: X5 s& ^# E
}
6 v- f1 P" t$ u( R/ [- a7 `$ gint String::ReadString()
. |0 q& n$ n6 F{* d) `, u% J, K: O7 o7 }' {
char tmp[256];
5 T: V. J) m9 y4 |2 U    if(in&gt;&gt;tmp)/ y7 t5 @. ]/ q) J" s' j1 J
{
+ b1 Y" w$ c& w  G  delete [] str;
7 W* {) {  r3 Z" O1 s  size=strlen(tmp)+1;: i/ t& Y% R8 {, l1 Y7 P
  str=new char [size];
0 r3 k7 k% f$ J  r4 T! v3 r  strcpy(str,tmp);5 M2 E) d% V% u
  return size-1;
- T" W4 I) S) h( v7 j" _ }- k) Q& }" H$ h0 c9 i& V
else
" Q5 ~9 r$ g) O: P: i5 w  return -1;
/ s- F1 ~* V8 g6 K' P" ^: W, a}
1 }6 J  h/ m2 g2 {7 Zint String::Rs(). A/ g- a! a3 C$ R& d7 p0 k
{
2 Z) ?$ P$ h" ~ char tmp[256],c;
) @' ~; |, o6 m% j! @ int i=0;
) m- ~/ q8 q. G8 _4 d" l while(in&gt;&gt;c)
: C; r: m: G3 i8 U1 \4 I {
$ ?: E, z) H# p% R; j* F  if(c!='*')
4 T' ^7 {$ w  z0 h! }8 H  tmp[i++]=c;
+ M6 T) o4 Z9 l! V; G! P2 J  else if(c=='*'&amp;&amp;i&gt;0)9 I) P0 l2 n9 a$ c
   break;; H. \9 ~5 l2 A" H
}
+ U4 m; q, T% t: |( K if(i&gt;0)+ Z- [. \) S$ C! v
{
! i! Z7 {. z- q: i' t  delete [] str;; P; j  {8 A' M8 b$ o
  size=i+1;
9 w8 C- K0 V! Y  _6 U" ~  str=new char[size];
3 i# \6 j( x% L+ _( M  if(str==0)& B1 K+ h3 Y0 R2 W5 Y# y9 ~+ o. b+ ?
   throw "error";( e4 L  n+ N) E: r9 `6 h% a
  for(i=0;i&lt;size-1;i++)! S5 ]: x- Y8 m6 B9 @! V
      str=tmp;  + J3 L- a; G0 H4 y2 F2 Y
  return size-1;0 ?; a. j) z3 [# g9 i" ]
}+ _& h" }: J/ h9 S. N0 k- C9 x, O
else
+ V! \: g! I$ d. D1 s& b4 v( L  return -1;
% b8 H7 C  l; ^) I: _}
7 C; g5 j& U- E; h; V2 R' T9 w* }void String:refix()% G4 H# D9 m0 r! D
{
. q) {; y  X* C' C/ t+ a' Z: U int m=Length();
' N, @, l9 u+ j delete [] pre;
# A$ w, ~" {! [# N# ^! \0 v  s pre=new int [m+1];9 N  Q6 {4 P, f" U) F( O+ @
pre[1]=0;6 N3 F9 a% n; ^, V% C8 W
int k=0;, b: A6 }7 {: M* z9 K
for(int i=2;i&lt;=m;i++)
. B) m* q$ \6 P) M. I# J {( G- @* z; K9 I8 i
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
& D  r/ [' c% r: M) y8 U   k=pre[k];( f9 V, E% B# \, E6 \( i
         if(*(str+i-1)==*(str+k))( H5 x: U. J4 H6 p+ @: M: ], C) w
    pre=++k;9 U$ L% r6 q3 ]) k
   else
. v% b  u. `- Z3 Z& m    pre=0;
- l' J% X" m( \5 A  l( u }
( w3 m  h! E$ H9 b2 K1 L}9 {5 F! A6 l( ^* [9 @; e; ^; a% I* J( y
void String::ModifiedPrefix()& ?# T  S, q  x8 K
{3 u' `+ q& ^* ?" W" d" Q/ C
int *f;. I5 ]! c% ]$ `" v& N- w
int m=Length();7 ]3 @9 l; o. h+ F: M& L
f=new int[m+1];2 \/ ?& F* n. ]* Q  t, N
Prefix();
& }/ w+ d4 ]  G3 `3 M  {) p for(int i=1;i&lt;=m;i++)
8 F6 s) p6 j9 m) G6 V" Y$ P7 C' O {% c8 W( `6 P" k$ ~: h: ^# H2 D
    f=pre;
" B7 ^9 u& ]' h1 g$ B6 T; b }
/ p" Y6 k3 C3 r7 v5 H& z! | for(i=1;i&lt;m;i++); h* E2 H) n2 v# W$ K. l3 ?
{, S3 O/ f; ]- O9 S+ V
  int k=f;
5 _+ e; z3 d+ [% x6 v; a& g/ I  if((k==0)||(*(str+i)!=*(str+k)))
# h) h/ W7 Y/ ^/ Y! V" A   pre=k;- Y  F! X& r6 ?
  else
. ]7 d# o, s3 O9 `7 a( W   pre=pre[k];
) O, ?3 K: X8 k1 K$ P& C }
9 _& ]' z0 \8 B$ A' V delete []f;
. H4 o& T3 H' F0 k! g/ D}3 G; l, O; M) r" D7 l$ D+ ~8 D7 ?5 E
int String::Match(int i,String&amp; t)
, ], O2 P) ~4 A7 o( l( M{5 A& C/ r+ M# A
int j=0;. C! I+ ~! O5 S7 Z% W+ l
int n=Length(),m=t.Length();
, U" E# ?6 T  B9 t t.ModifiedPrefix();4 S, I, h/ Q( o8 Z6 A5 ]
while((i&lt;=n)&amp;&amp;(j&lt;m))- a/ e, c  z- m( D! c2 {7 ?
  if(str[i-1]==t.str[j])  e4 K+ h5 B3 n( p& S$ v9 F
  {: V. R; K6 q: O$ L
   i++;
4 v0 s+ I! L$ M( B0 {   j++;
2 e6 n6 W4 U; c6 q- D: g, y  }& _* S2 i+ E0 Y" L
  else
4 R$ K& w0 @1 @8 @1 i   if(j==0)
- v8 `" Y' b. i/ D        i++;
* N* Y. \1 d7 V# {! m      else & ]9 T1 ^/ Q9 B% H5 l
    j=t.pre[j];
) k( w; ~$ O  ~  if(j&lt;m)/ }+ S. n* `2 D/ X  q
   return 0;# x5 \0 ]" O, {3 S: J1 w, O9 k2 g# i
  else
# A/ ~4 c/ T. e4 `   return i-1;# B9 @$ T/ N- _
}& {$ X2 I/ n9 H& y! [( B$ n: g4 d
int main(); Q& g: ?8 S. r$ `8 G
{( n/ Q0 E2 b, {% k2 F; _  g* t
if(in.fail())
+ t# w( y7 C$ n/ T {' M. M+ K! Y- z+ l' N( V
  cout&lt;&lt;"the input.txt is not exist!";& P: \) E! c, A/ a4 \, Z6 D
  exit(1);}
- u! \& B9 _$ R1 ~" Z" s int i=1;
$ p+ m: C- K/ A8 ^/ [( Y, s7 t String s,t;
& {9 R+ c( K- b7 {  F s.ReadString();6 ]3 M6 G4 e1 P
while(t.Rs()+1)
0 p) d- i! G& a0 F' O5 Z {# A( d& r4 y- D$ t* L9 b6 ^3 r
  i=s.Match(i,t);
; F0 v5 R+ J( \8 z  if(!i)+ o! G. X/ |6 j% L' h$ k
  {9 W% a: @+ m& Q: ^
      out&lt;&lt;"No"&lt;&lt;endl;5 F2 P: R, d" X5 X+ z/ I: t
   break;
& A  H7 G4 t7 B* i  }
8 q) R0 y+ M7 [2 D% x }% F* Y4 \2 I( W/ D3 |
if(i)
( e4 F. g1 K: V3 q$ e% c  out&lt;&lt;"Yes"&lt;&lt;endl;
  n% H3 Y2 H( I  u return 0;, e9 j) L3 c# b$ I% ?4 A
}

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

62.99 KB, 下载次数: 10, 下载积分: 体力 -2 点

间隙字符串匹配问题（c++)
作者: zidance    时间: 2007-3-16 23:03
看看啊
作者: sgnswb    时间: 2007-4-2 09:59
顶
作者: ari0101    时间: 2007-4-3 11:30
谢谢
作者: hyacinth13    时间: 2007-4-5 19:56
<p>谢啦~~</p>
作者: zhaoyunfei1126    时间: 2007-4-7 11:39
好吧[em03]
作者: ottiou    时间: 2013-5-11 16:12
看看看看看看看看



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5