数学建模社区-数学中国

标题: 间隙字符串匹配问题（c++) [打印本页]
作者: lynnyan    时间: 2005-4-22 01:37
标题: 间隙字符串匹配问题（c++)
<>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>2 l5 B" [+ {5 |  l
<>[[/hide]</P>[attach]1460[/attach]#include &lt;iostream&gt;
# O' K! ?$ r0 @: q, b$ n* k#include &lt;fstream&gt;
" C' j# _& T8 s7 M! N3 v9 qusing namespace std;  a+ B2 e8 _, C' B8 P3 M5 Z
ifstream in("input.txt");8 z/ Y( x% _: }8 u" W
ofstream out("output.txt");
2 m) M. ]( b: Hclass String7 p8 t* K4 `, K8 }" z1 E
{) X$ W7 ^3 N7 x7 m& M, Q' I$ e
  public:4 X& d! S+ |$ T, B3 T
String(char *s="");; t/ S. d0 Y. Y1 u! W* O7 s& e
String(const String&amp; s);
0 a# f- g) j/ G" B/ ]7 W ~String();
, e8 y; W! A; n int Length() const;
6 B- [1 q9 Q2 }. C int ReadString();
. S% \3 E; e$ a int Rs();3 G" ~! w: i  @* Z
void Prefix();
5 M8 e, t- z" {, t3 E1 E void ModifiedPrefix();
3 C$ \% X" v3 C. K0 H: K int Match(int i,String&amp; t);
: R' N3 m; ]( b8 w, w  private:
, w) I5 h/ @: [  ?/ m6 F   char *str;
6 ^; z+ g$ W6 ]" e   int *pre;
8 T& z6 x: ]2 [   int size;
/ h$ m, }9 R6 R$ [};
. @6 p" d) b! u+ D8 uString::String(char *s)- _5 V: ]; M' ]  h5 ~, {- V* u
{
2 u' |& z) [5 ?/ j size=strlen(s)+1;, K* _+ b. u  t
str=new char[size];
+ k# k* n+ p8 O! g' G/ k if(str==0)
0 F0 y  ^" Z1 W( |  \0 [2 o/ p  throw "error";
/ U0 p, r8 l) H( g% g3 J strcpy(str,s);# d$ @; p# w' M. E, e! t
pre=new int[size];
$ D  r/ {" \4 A! t$ `$ K' U1 @8 v if(pre==0)
% R: \$ r" w# S1 p# a" j" y/ K  throw "error";
# {) `. {2 A" K9 @8 k+ \}
9 {: ]$ s# t$ ]! ^String::String(const String&amp; s)
6 r* l7 U) Q; m3 c# g2 w2 j{
$ E/ z0 z2 E& s/ P& J5 C( T7 j size=s.size;* n* H6 I% q: X* F% a  b
str=new char [size];
, z9 M) y; H; \  J. |% t* p if(str==0)# M4 ?% c* Q6 A- A- \
  throw "error";
# i) W5 ~8 O# @8 ?2 y8 E strcpy(str,s.str);# F) s' z' M# n. v0 o9 [
pre=new int [size];$ Y' Q% J/ ^7 B# ~
if(pre==0)
( c0 F" D. F# C# e- h3 u! T  P  throw "error";& d9 K0 Q$ p  j' i0 I) K
}% `8 [6 g# h) h2 M* D0 v- g
String::~String()4 U9 t2 P' K& Z( i4 k5 O* ]
{6 Y7 L) s$ q; o% d: X( M
delete [] str;$ X4 r; M. Y0 v9 \! A
delete [] pre;. ^( O. f$ ]* I) v' @* J. K, ?
}& l' ]0 d# R9 h! d# ]
int String:ength() const
* s* o" o1 R! Q1 W; e9 j6 {; d& O/ v{9 b4 D+ E/ L1 j+ a8 d# {3 t
return size-1;
# K/ j3 I/ Z7 ?, u6 C2 e  H3 J}
, A# \0 _: b; T" s1 f/ [int String::ReadString()
' p. C- K' b1 U/ d/ r6 r{
* R0 _: p3 _5 R, T6 C% B, p char tmp[256];  t# F0 k  b8 g  g% o+ U9 k
    if(in&gt;&gt;tmp)+ u& W6 I3 _4 X) v: S
{, x$ p1 }7 P8 u/ d: N
  delete [] str;
) l+ v4 k( ^0 y  size=strlen(tmp)+1;
$ e8 J4 c( Q0 C+ d  str=new char [size];9 [2 Y9 J' }7 A  V( L
  strcpy(str,tmp);
, |2 q8 K( k5 _; f# _  return size-1;
, ~+ c) e  l& G7 z }
2 Y8 a( D) w6 u; X; r else
! k- _4 N' `1 H  return -1;
2 U" e$ X% L+ n* Z: C$ r9 U}
, @# e- t4 L) W4 g4 xint String::Rs()
5 c7 [6 S4 _6 s) x* _& T{
: l; O; A3 n0 Q4 g2 D2 h0 Y char tmp[256],c;! ?" m  U5 R) G) k) E- t
int i=0;
3 Y0 U( F0 P3 H6 V% g. u while(in&gt;&gt;c)8 R( X% Q; \) R2 f  }' s
{
# [4 j% g, \& {* q; j. g  if(c!='*')! M2 D! s4 h+ R; T
  tmp[i++]=c;
' O9 J* n4 q5 {6 M8 B) {  else if(c=='*'&amp;&amp;i&gt;0)
) M' N1 g" [" [% X   break;! m7 R8 j1 Z$ T9 t) P
}
0 W! H# M/ ]; s, ]; p2 e) W if(i&gt;0): N5 k( i" U7 ^& D! {) Y8 m! u
{  D" g' @! Y7 e, g; b
  delete [] str;" |! q7 i6 b* t& D5 e  C. V3 A$ I
  size=i+1;
, H* X2 S" S! r+ \$ q2 b  str=new char[size];- Z' P* d8 R5 x! {/ M
  if(str==0)
: d8 z( f- o9 I   throw "error";( ?( \+ O( f; i" r6 k( B
  for(i=0;i&lt;size-1;i++)
. T& i8 q% R$ d8 K( x      str=tmp;  ) ^; p# n4 q9 `; p
  return size-1;
. b$ z! q5 n# R }& a9 ^* g' O- T8 A4 M! B6 d
else8 x- w. g: K. e" E4 b0 D9 f
  return -1;- p9 I+ b7 e, T" Y. w! P0 O) }
}; R! D5 J+ k/ L) x
void String:refix()! }& `% L% K0 h' N6 {
{
' L; Q5 x; p. g8 @* ?/ `$ p int m=Length();6 y( x& q" k9 a; y* C6 o
delete [] pre;. Q0 Q! Z7 F# ?
pre=new int [m+1];8 B: X' k+ `4 U9 A  D* N# _/ Q% p' B& o
pre[1]=0;) i, s; g8 e# W. X2 _
int k=0;! N4 O" |0 Y+ a
for(int i=2;i&lt;=m;i++)8 r- M& y, Y( D, `9 [8 I  U1 A
{
" T* R2 C- Z- P% d  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))0 i6 f* r3 F( v( w4 e3 T
   k=pre[k];8 M0 J7 l" x& u- P  H
         if(*(str+i-1)==*(str+k))
2 K9 w2 H$ K/ u* Y* w* p    pre=++k;
- E9 N6 ]' _; ]4 p% d( v! [   else
1 n- m: H  m8 I4 N    pre=0;
$ h. h  n2 x' d' d- Z }
; I& h/ t. s- k7 o# S! U6 i}
0 g2 v. \- h# {7 @void String::ModifiedPrefix()
1 I! ]3 p1 D9 X# _. S{' k3 W" ^/ P( T! t
int *f;0 ^6 s: h  [! ], O! N
int m=Length();
" K4 }, F9 n3 A3 p' p9 l3 i6 T f=new int[m+1];
3 f# k/ [1 ^4 h; j. Q: R1 a+ v Prefix();
: d% h6 o  h: d4 a9 K0 S: ~ for(int i=1;i&lt;=m;i++)2 H! z, v% O8 R0 t8 B$ i
{
8 M' |3 Y3 Q2 I5 n" J5 n    f=pre;6 \  I  N$ p9 {. {- O
}5 L3 w7 h2 ~: A6 M: w2 o" |6 x
for(i=1;i&lt;m;i++)
, T" g4 y1 D7 ]- ^; U2 h9 s6 A {* r: e2 E4 e- Z$ z
  int k=f;
$ J% V3 M4 r8 ?5 W  if((k==0)||(*(str+i)!=*(str+k)))7 J$ \1 p5 K) X
   pre=k;
9 m7 ^- o1 X1 a! B! w  else & e0 E0 N3 t' ~* I/ k. P8 V) A
   pre=pre[k];
$ N/ @: K" |. @' t6 b/ O$ M }+ {& p* l0 u" u  E& x" t" \
delete []f;
2 F1 ^- ^7 I0 |) f2 _: @}" _3 u, Z* Q* H. X4 F
int String::Match(int i,String&amp; t)
  H7 g6 p0 H) K  H. u. F. u( Z% ?- q{
8 X5 U/ j- L0 J! h1 t- m" n2 @0 Z int j=0;
- e9 C3 p0 n3 U" X/ A* i int n=Length(),m=t.Length();  D( r" ^8 x1 @4 [
t.ModifiedPrefix();! d' Q& T, b% g6 ]
while((i&lt;=n)&amp;&amp;(j&lt;m))  i: P; J; f! Q8 l0 H7 j
  if(str[i-1]==t.str[j])* n0 m- \" |5 M9 x% T) C: T
  {" U: v; w! n$ q. c8 b
   i++;
$ W7 p6 q& j1 y   j++;  j- R* T; L  b+ l* B# b. z
  }
7 s9 i0 L3 C+ w# X0 ~9 l  else
4 E% Y! y- Z4 n   if(j==0)
  L. S1 f, S' u  e        i++;' R2 E5 t; C* @3 n
      else 8 @3 h; r6 c& u
    j=t.pre[j];
* ~" o8 S/ ^5 v  if(j&lt;m)
/ H: o7 P% T5 }9 @; P   return 0;5 b# \% I: G; Z; ~4 [# i7 G- e. P& W( B
  else
3 Y: v- r. a2 |  s   return i-1;
$ H7 p4 m# r. E7 j, a$ s2 b" ^}
, n$ I; q) G, x4 `& l0 Iint main()
4 ^9 |* H6 q" H5 [4 p) Z5 r{
) X! r+ u5 A, n+ @7 e- E0 z if(in.fail())
' D* J* z9 N+ M9 f$ `. R {+ l: N1 ~1 G3 E/ V
  cout&lt;&lt;"the input.txt is not exist!";* m" v' _' t: O; u9 i
  exit(1);}: ^1 p$ u- c% [: I! _
int i=1;1 _" O: N4 x7 ]1 }7 h2 k
String s,t;  h4 @( t; m$ o7 {+ d7 O9 h
s.ReadString();8 I% S  \7 V9 S/ c' S
while(t.Rs()+1)# m% I' O! d* h0 \; u
{1 Y# ~& B- b/ U7 |  V' I- a( }( `
  i=s.Match(i,t);' y8 Q! K, t+ S( E4 Z, e  q4 l
  if(!i)
  x! k! p) j( [' K6 t7 a  {
* |' c) _* O+ ^( I      out&lt;&lt;"No"&lt;&lt;endl;- E4 c9 E5 D) ^* c1 }
   break;. i) e. w* O% y1 D- k
  }7 x( d0 ]+ X0 N- O( z  \
}/ h+ s1 i4 @; L! U; Q1 o
if(i)/ o7 s! s# o6 {0 m( X
  out&lt;&lt;"Yes"&lt;&lt;endl;3 p  c( R5 h) o; c! w3 x
return 0;* r" t5 Z. v. k4 c) C( Z8 l5 v
}

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