数学建模社区-数学中国

标题: 间隙字符串匹配问题（c++) [打印本页]
作者: lynnyan    时间: 2005-4-22 01:37
标题: 间隙字符串匹配问题（c++)
<>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>
+ X* X/ l% v5 l% q$ t* z9 o<>[[/hide]</P>[attach]1460[/attach]#include &lt;iostream&gt;
+ |* m1 {0 a. h  b- o  K#include &lt;fstream&gt;
+ [( _/ s( N1 O0 f8 Uusing namespace std;
9 w# M) R+ H6 C7 x! qifstream in("input.txt");3 k% h# P1 n! O0 e. F& J9 Z3 }
ofstream out("output.txt");
, t% g$ J- R4 N6 {! H: R" bclass String/ P; ^  P0 e1 p  J2 ~; a8 T3 J' v
{# C  C5 B0 v& s) G2 }* G# R7 G
  public:
, W/ G1 V* e! Y' @, M String(char *s="");
; a/ O. S, l8 S+ y! B2 k2 l+ ` String(const String&amp; s);( _6 [( @+ O# y
~String();
- B* k8 ?! |. @ int Length() const;
' i( K7 z8 L. S/ \1 ?) _* i; f int ReadString();
6 J, N3 v) a' i( _5 f( \ int Rs();: s* A! Q+ b. n9 A/ Y$ m6 B; m
void Prefix();
; L3 L' z4 p0 `: @3 J% j" N void ModifiedPrefix();
6 w# F1 H: e* ?1 C" }) ?' a int Match(int i,String&amp; t);
) a: @+ g9 T9 H1 J  private:' w8 h$ ^7 e% i) ?! S: i
   char *str;0 |. n" O9 L- ~
   int *pre;+ U4 E# ?% q7 b+ e
   int size;
3 {1 w' }; T5 |8 |4 E( s};
$ P' m/ f1 i* y/ `4 tString::String(char *s)$ n" i- ]* i* I5 Y& S' r0 ~& J
{
4 a4 g) d. I0 g# G( J" M size=strlen(s)+1;2 H, j- D, M2 d3 X, i
str=new char[size];' I/ U4 K2 {7 H4 [& P) u
if(str==0)/ I( |, G; J6 ^: H* E
  throw "error";3 o/ Z; Z7 h5 S) Q
strcpy(str,s);
" E5 s6 Q4 y0 i. D# z# s pre=new int[size];
$ C1 e6 W8 P) t9 E' c if(pre==0)8 R  g7 q# L4 b- x8 b9 N
  throw "error";
5 }2 R0 S* B2 h' U0 v}
8 I/ H" k$ D9 sString::String(const String&amp; s)* {# {; K5 W+ z; L: G3 H) P
{
, d1 I8 Y2 V6 t3 f0 Y7 ~( h size=s.size;
+ ~2 ]1 p: l; {8 x str=new char [size];2 W$ t4 s6 I2 \  ?5 H$ H
if(str==0)
' g0 Y! j; l  f( q; B5 T1 |  throw "error";
0 k# e7 |: G4 S% ]2 C strcpy(str,s.str);
: g0 h8 X# @$ }4 s9 v+ d pre=new int [size];' e8 @# I* p2 X( m2 N$ S* d$ _2 S
if(pre==0)
& ]/ {2 l8 e- a- }  throw "error";
& @) o+ }; \" a8 F8 s3 A}
7 ?9 k' i0 d! \% z# CString::~String()
$ x- S; N" z6 O/ y7 y{
& b" Q5 L1 M- ?/ d4 [0 ` delete [] str;
/ M. [+ c! Z+ U0 u3 R  `7 g delete [] pre;0 @2 }1 j  ?% ~5 l* v) V
}
7 a& T. J9 W8 N2 v% W  Y5 gint String:ength() const
: x# ~! C. }: A{2 S8 y, n3 C, Q, b" y! i' m
return size-1;
/ D' K) ?/ s4 p$ d}
1 a9 ~; z0 q* Yint String::ReadString()8 d5 ~% B/ y4 n8 Q# x4 a0 ~
{
7 [' i  A" [4 P char tmp[256];: Y/ u& B. Y1 i1 W" J) h4 I0 O
    if(in&gt;&gt;tmp)
5 U. \$ [5 H$ D0 \$ c/ ?" ^' q {
4 t2 B  @# x8 `4 `  delete [] str;
, p3 [2 b- B! ^* K  size=strlen(tmp)+1;
% y& k. j5 Z+ W+ Z5 m/ B  str=new char [size];
/ A7 b  X; K7 Z6 M6 a1 e  strcpy(str,tmp);& c1 ]& i2 T4 V) N$ b1 Q8 T  W
  return size-1;
( Z5 U2 L! t/ Z0 ]# {5 j4 S! K1 p- H }1 J- k% K) D) u8 b0 ~% I
else
) @) a% x, Z( e. b  return -1;5 I: x0 f2 G4 L) h; }% S/ H: L
}
) q3 t! V6 {8 L, Iint String::Rs()% o0 C# z* v9 m
{
8 X- K1 W! X$ g' J char tmp[256],c;
8 l; f1 Z/ x" ^0 G+ C' ]7 ? int i=0;
, U; S. t1 P, L8 Y8 j8 C while(in&gt;&gt;c)
6 M, H. }% }3 \/ w {3 @% Q5 |% d- S: b! Q
  if(c!='*')
4 B$ n$ Z" q8 ]* n. B& X7 V  tmp[i++]=c;# X6 V3 c; a; Q6 K
  else if(c=='*'&amp;&amp;i&gt;0)8 U' i* u+ L( o. q
   break;
% z. C( D$ D% f5 _6 N; G5 I }
# h. Z5 i% l7 w0 Y0 E) I. | if(i&gt;0)
. ]& `( P/ z/ Q8 ?( ?! S" k* W {
) Y! e* ~, {: Z0 _! {, s! j  s  delete [] str;
$ @5 s1 e7 j. L" l( A  size=i+1;
; P$ L) Z0 Z, g# j  str=new char[size];
3 ^  y4 M+ n5 p4 e1 m5 X  if(str==0)* J! Q* c' {' c
   throw "error";
/ ^% D  u; Q2 j, U& f. Y, _' f  for(i=0;i&lt;size-1;i++)9 W, `6 S! c! j$ U7 Q4 a/ |+ Q
      str=tmp;  8 N/ d" m. v- ]0 U, K+ U
  return size-1;; R2 _6 p+ ~% \5 O, c/ P
}
$ j# h  L, B# j7 T else2 ~/ L8 i$ B4 w5 p: Y
  return -1;
6 T* [- O8 K+ D( s}" u$ p, |- H1 F0 ?; s
void String:refix()
4 u3 ?0 i, l& M{8 _0 p5 V- t- N8 c6 T9 x
int m=Length();
0 R- e, M/ a9 r1 N5 `: t" I2 U$ B4 h delete [] pre;8 |8 e3 x  l0 V2 [; U( C; Z/ S8 `
pre=new int [m+1];
7 M( w- `& f# u. ~+ w: i' O pre[1]=0;7 x. ]" a: `' B  m) e+ f3 J" v
int k=0;: {# ?* e5 U' k
for(int i=2;i&lt;=m;i++)1 g! t. L" t2 p! p; ^- J. A9 {
{1 R; j4 i2 p' o) w( }7 K& x1 Q1 o
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
, `  c" b. b: @) M- C3 m3 B% k   k=pre[k];
8 A5 |) \0 D- A* `1 i         if(*(str+i-1)==*(str+k))
! {& N  M, m3 I3 f    pre=++k;9 L; S* {5 Y6 A8 W
   else
% d/ r6 U2 h0 U* T/ G  o: l    pre=0;8 t- J, q  B5 T: h  n& \
}
  \) a* D3 O, o4 ]}
2 `1 L+ @5 J' h# T, }void String::ModifiedPrefix()2 d5 x1 W! M5 B
{, D  d6 o6 {( n- p" c
int *f;
( q* d3 _( O: I: |6 p' u; f int m=Length();" ^( V) a0 @/ ^3 R5 P( f$ h2 x
f=new int[m+1];
8 O/ d3 \1 r9 U% G7 c Prefix();0 d: e0 E' S! {3 o
for(int i=1;i&lt;=m;i++)7 [* Q% r7 k+ I( k0 y
{4 ^1 {: S/ K( {0 ]% ?7 A* n! `
    f=pre;& Z* V, f+ f% z" E* g0 F
}
8 ?* Q. G+ o* H' K- v: [# m2 s" a for(i=1;i&lt;m;i++)9 h' h5 n  b6 @7 W, g
{  |) J( i, z7 D+ N" y( t' W' z- H" M
  int k=f;  X( x$ r! s2 a( D! N4 b0 H9 o5 J
  if((k==0)||(*(str+i)!=*(str+k)))4 ~% w6 F6 N' L1 _' h% k
   pre=k;+ [* \& b3 l+ K9 `) p" B
  else
6 O' i4 n, Y6 Y5 a9 Y' F- }& g   pre=pre[k];
5 A4 a& i- ~' A }  F" p! S% G2 J! n; q' }# t
delete []f;. J$ D: Y$ x  A$ D5 x
}8 l1 E+ w2 i7 k' e
int String::Match(int i,String&amp; t)1 d" y; X3 @5 J" s) H
{! ]) J" e: r: t& [% O4 ^! C, ]
int j=0;1 N2 [2 w" v4 q% o2 Y, K
int n=Length(),m=t.Length();
. S) k. t6 ^# `; a# M; C8 O3 f t.ModifiedPrefix();
% u$ A* H3 d1 M while((i&lt;=n)&amp;&amp;(j&lt;m))
2 N2 [5 t. n6 L  if(str[i-1]==t.str[j])4 E6 ^6 p: \5 e5 H+ E( l* R& Z) T
  {" ]' u0 p% g: ^4 \' U5 G/ z8 s% K
   i++;; e2 O7 |' S3 \7 _! d: e! k6 [4 O0 |
   j++;/ _+ A- Z* G9 {3 r/ k9 t
  }
# s" B5 I) `# ~% c% z  }  else 8 ^+ [& U5 y6 X  @
   if(j==0)3 a! w2 U" Q: C% ^) n* t
        i++;
; N2 D3 }, B- a      else $ P9 m. |( p* I; c5 }* {3 J
    j=t.pre[j];
' T+ _; W% b0 S8 a1 m. x; c" Z  if(j&lt;m)$ A, z, R% T: e- k% ~, s
   return 0;, p9 H8 R% t. E
  else
9 t6 a& Z4 O! u   return i-1;# t0 r. ~4 n& D$ o$ Z; ]+ h0 g
}( D0 A" l! X% v! o+ K" ~+ R7 L
int main()
) ?) Y- U* a. q: f5 L; q' U6 w& K{5 k' L$ S  G8 `" u9 e+ u
if(in.fail())8 I7 c7 |0 k( {( s
{
9 L9 m- D8 W. n8 F7 u: m+ h  cout&lt;&lt;"the input.txt is not exist!";
+ H5 v& x9 Q5 _" I4 m  exit(1);}
! Q/ L8 P  \+ z8 M0 j3 q int i=1;: w" i% r. z6 i+ S6 w6 I1 l
String s,t;5 |' I% }8 o, J/ ]$ N! N
s.ReadString();
3 ?/ F3 q# P6 J  _4 d5 Y while(t.Rs()+1), p6 m) ^/ D  n
{
- m* s* Q2 q$ H( Z  i=s.Match(i,t);9 d! _& G& r" W; a& u6 u+ A
  if(!i)
, C, ^! _- B8 _. ^  {/ c  g3 n' Q2 Y9 z5 e/ |: {* l0 U) ?
      out&lt;&lt;"No"&lt;&lt;endl;
, |; |# F  r3 r! T. d9 R   break;
/ c& a8 u* a* f  n0 `) g! x4 E  }
# {( a& C6 `" e, f9 M* Y }
6 m9 e' w" j/ F: G) R if(i)
/ _6 C6 i' a, T# l  out&lt;&lt;"Yes"&lt;&lt;endl;8 l: r1 u" Z5 t
return 0;
3 \$ a9 ?: n) G  g# j8 W( B, n}

间隙字符串匹配问题（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