数学建模社区-数学中国

标题: 间隙字符串匹配问题（c++) [打印本页]
作者: lynnyan    时间: 2005-4-22 01:37
标题: 间隙字符串匹配问题（c++)
<>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>
) M! \& |. `* L& ]0 x<>[[/hide]</P>[attach]1460[/attach]#include &lt;iostream&gt;
2 J2 e) n% P! L% s( o9 @; I#include &lt;fstream&gt;" J* l- \: c* G/ w; J4 p' N
using namespace std;
/ ], u- s( [) X& u! W9 Difstream in("input.txt");
3 Z! S0 Q5 g1 G% }0 [' uofstream out("output.txt");; e6 K+ H2 [& i( a5 g3 Q
class String& H6 A9 I; n) B# ~6 Z3 ?/ l2 Q
{2 M. y; Q" `* v# g3 b4 v, P0 p
  public:3 P) p. u' B3 B$ N7 y  O& E
String(char *s="");
9 D, i! T/ e" T3 t: u String(const String&amp; s);; L2 b/ R; m2 }0 |) `
~String();) U' w1 G: @5 C# k
int Length() const;
1 c; L& O0 z, e' Q, W/ @ int ReadString();4 t7 j  N3 i9 A3 A( q
int Rs();
1 b) _* P7 k' U8 \ void Prefix();* r& d  |5 ~* w! z2 A3 g# l+ D
void ModifiedPrefix();
! Y8 D% g) O7 H! w int Match(int i,String&amp; t);# b" B( Z8 ?: s+ L7 s# |" u
  private:% z7 ^4 V5 C( N8 J9 {! ~+ u
   char *str;" j/ L! N1 d+ t7 i! @. Y/ T& j
   int *pre;
; y! J7 m/ B. q1 f; q* \8 H. t   int size;
0 l" m8 J) r7 ^' r, h/ E& y};
5 v" v, s7 T/ p" AString::String(char *s)
6 R" N" m/ x. U8 u9 ^{, N9 L- g- z$ m& v
size=strlen(s)+1;) _0 Q8 n3 d5 g0 X9 Q% B9 i+ R
str=new char[size];. G( O: v, B, V( C6 `5 u5 c% Q
if(str==0)
# [$ o* ^9 K5 E6 q$ T/ d& r9 i  throw "error";8 C9 x8 g4 S) s9 y4 a
strcpy(str,s);6 x8 N* t2 c2 `9 z' L- b$ A  P  L% j
pre=new int[size];
" \9 d7 L! t' g# J if(pre==0), c/ T# A& G* p6 ?1 @+ x
  throw "error";
+ Q% T9 n3 \& A$ l/ ^}
& L- H; ~% j; pString::String(const String&amp; s)+ K+ {# {3 p+ ~6 b
{
8 O2 x) k! @+ v% p7 G size=s.size;
; K4 d3 c' n' [7 P+ \% S6 ^ str=new char [size];: u5 ?! d/ z9 d+ d
if(str==0)
/ K! w& V- y; B4 W' @) F" F, e  throw "error";, n6 S9 C. A* J8 d& K( T; e+ T& B
strcpy(str,s.str);
& G( O, T0 H: b) k+ n pre=new int [size];
0 C( H# _0 ^1 R if(pre==0)1 o( r9 N* Y) f4 a4 [
  throw "error";8 I9 p# r/ G+ D
}
. F" S; b" e0 Q+ SString::~String()7 @2 v# y  w0 h6 G( n& K1 r
{
. G7 A; ]  U; B delete [] str;
4 U, f4 L9 a) [  q0 J delete [] pre;" f5 U. ]: t4 T
}8 s  H3 _* w3 k- @6 y" p8 [4 O0 e
int String:ength() const' U7 q3 G( Y7 b6 e* O/ L7 H
{
+ B! }5 ?' N# I1 P# b: x. _ return size-1;4 m1 U1 s4 H! {, P( x2 ?
}) t3 `0 o; Y- N7 c8 f+ w
int String::ReadString()
7 }3 L0 `0 n8 x4 {: a0 m$ o{
7 q6 G( ?/ t* a+ B( r; S2 { char tmp[256];
) W# M5 P+ s0 D    if(in&gt;&gt;tmp)
. k* M  K, k8 `) P( E {* O" i) k2 y$ `
  delete [] str;/ q! N! q3 y2 ^
  size=strlen(tmp)+1;  ^( G3 r' E/ R) B2 k
  str=new char [size];
0 s0 O: ~1 N7 G& @. o6 ^  strcpy(str,tmp);
- s8 g' M$ b4 C; H( e  return size-1;3 ?! P* D4 g# Z7 U, B
}9 j/ g3 x- G2 F% F- o/ ]
else' b) z  ^2 R/ f1 [6 g
  return -1;" d8 x, C, N8 f/ @+ U
}* j* \- C- T4 S3 e+ V/ x' N
int String::Rs()
& e7 g& P- V* M' C; u{
& k* v( k& @$ `1 P7 }$ { char tmp[256],c;2 R/ F4 w6 p8 X3 h, k1 f, `
int i=0;
' a. r# g! X' I" q' V while(in&gt;&gt;c)
5 _" P. t0 Z) i" b# T {
3 F1 F/ m6 s. z) |2 O  if(c!='*')
! v+ @6 Z, D) e2 s# G  tmp[i++]=c;$ C0 P2 f6 F1 t) Z1 z
  else if(c=='*'&amp;&amp;i&gt;0)" {1 P+ H0 L& v9 G3 X6 |
   break;
9 W: q1 l; \- E }" h4 O2 {8 B" U2 \
if(i&gt;0)
' u& R' _5 r. W* H$ v( A  K {
) P& H1 E6 q8 A6 g% b5 f  delete [] str;% P3 ]1 k% T2 b# r) p9 M% N0 m
  size=i+1;$ c5 w. h7 o+ s7 v6 F$ \
  str=new char[size];/ n- o$ J. R0 _  S$ L. Z4 D
  if(str==0)5 E; n+ z9 W4 I1 @: E; P
   throw "error";
' S1 ]3 i: d  O" Z  for(i=0;i&lt;size-1;i++)
) F( H# i0 |+ J8 }4 @8 Y% J- g0 m  d, [      str=tmp;  
; S2 a9 o1 Z" D* C# l- T* h  return size-1;1 e+ z0 p! F# K" Q
}
# D% P  [( r0 C/ |0 Y# M else
0 q6 L* q  Q% z* A7 Z% \6 ?/ n  return -1;2 b. A: d/ g' w7 m- L
}
2 Y2 Z! m7 N# ?2 i/ b* }! tvoid String:refix()' X# o) x( f2 n% c. l; t7 s' S6 t
{
( K7 u5 d. m- e$ N int m=Length();
2 A: x% T0 p1 u2 D$ T0 [2 C0 J delete [] pre;% h+ m1 J2 h" g: {+ R
pre=new int [m+1];* d: D- `- T9 y3 ^- f9 M
pre[1]=0;6 Q9 k0 i( ^& z* n
int k=0;
" e& G; g, h# P+ m6 J& D# x for(int i=2;i&lt;=m;i++)
6 f( @3 q% z+ E {
; ^  f% B* ^0 B  [  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))$ |# ~: ^# s; B' d7 S: }. D, J
   k=pre[k];
3 d9 Q$ Z7 y5 f, B) M& N         if(*(str+i-1)==*(str+k))) T& p7 V8 q( W' l% C
    pre=++k;
9 V4 g, P; i4 `- C* h   else" Y) g+ d: Z* ?5 H
    pre=0;! u1 D8 e* A4 C5 Y! N
}+ t6 x3 q6 j& I% }8 @! }$ h
}
7 |/ W( W1 \" p% i# D% pvoid String::ModifiedPrefix()
) w, @+ y' F- ?* V$ g{
' n% ]$ h( _, b3 W, W) g( D6 _ int *f;
% F" b9 B9 r; v5 P int m=Length();) S0 P6 J; k+ z; G
f=new int[m+1];
" R+ b8 u/ [2 Q& i3 T; l2 |/ V8 h Prefix();5 Z) u; h2 s8 N  \3 X# e
for(int i=1;i&lt;=m;i++)
3 H0 q. A0 {& U {
, {7 s3 L$ P4 \8 s    f=pre;
& ^  {6 T0 R* K8 w3 T3 q# ?6 F3 R }5 j# R! ~9 I4 N+ \6 l5 d
for(i=1;i&lt;m;i++)
% [/ t  P/ E8 q. m {" g& a' Z& p1 d+ z4 B) s0 Q
  int k=f;" K$ X( J+ I: F/ t9 X! T- y" L
  if((k==0)||(*(str+i)!=*(str+k)))0 t4 n, R3 i  P/ E
   pre=k;4 `. w; j; M+ P* S5 l( A! g, \
  else
, w# n0 g  B6 [2 e& U8 g   pre=pre[k];9 |% h2 q; w, s+ O3 `
}* U' O% ~4 c% x* s3 r% H- V- F
delete []f;
; b3 ~( z" v3 w( `5 C1 F* b}
. o8 x9 P' p: O3 O4 Q0 k4 bint String::Match(int i,String&amp; t)- X7 h6 W/ g0 r0 [3 ^/ L  |; q) s: a
{
1 E# o- Z+ Q, C( X$ i int j=0;
* G6 @/ M7 v7 d+ G  ]; E+ W int n=Length(),m=t.Length();
- S4 b2 d2 \) F# y" j t.ModifiedPrefix();' O9 _: [# Q# w1 r+ b1 ?7 H0 G
while((i&lt;=n)&amp;&amp;(j&lt;m))
+ E: ]1 C) G1 Z& e  if(str[i-1]==t.str[j])
( y! N; V4 y/ V) p  {- x8 s5 N& f7 o4 O: j8 V" j
   i++;7 E' c5 j: \" A6 {/ k8 l
   j++;
0 r: `! p" Q/ y3 s  }, B7 B) z0 H( j7 O+ v. P% S
  else ) s( ?) M* U8 Z" s& w2 m
   if(j==0)! `" j# |: K6 Z% J% f5 B' V! H
        i++;7 ?' `" @& B% H0 X/ `# @! z
      else
+ p" {5 i: W* P) _( Z1 t/ q    j=t.pre[j];. Z5 ~! s" c. F
  if(j&lt;m). |. w4 M4 _; V/ r! k1 ~
   return 0;2 D% u6 T/ z1 ?% e: n
  else
- z3 e: t4 ?  y& Q9 N   return i-1;
5 G  s& {! r( e  M  E% K9 C: K}6 |- Q' I" P- A8 i% O, U
int main()
8 N9 C# j* j: N+ D/ H. I# R- b* k{
9 }; D. [/ _% P if(in.fail())  ^& X9 b$ Q% h  t
{* f- ]% a2 x; J$ t/ }% G) }  k: N- H
  cout&lt;&lt;"the input.txt is not exist!";
4 M9 F, v2 r; Z/ A8 R1 R; C  exit(1);}" V; C/ V4 o# h4 |* h9 G+ Z$ b
int i=1;
# x8 t" S4 e( f" { String s,t;
$ o' v- S3 o; s1 O/ x s.ReadString();
. C; G1 A; G! \1 N: J6 P while(t.Rs()+1)
; ]" I  ]- t: |! U! e/ B4 T {
) |5 d9 V% B9 W( }& z# ]; [  i=s.Match(i,t);
( J/ v/ ~7 N0 I" u  if(!i)* `$ r# k( A* Y: v2 z/ A% ^
  {& c( }* O. x' i4 g3 X
      out&lt;&lt;"No"&lt;&lt;endl;8 w! {5 F' m6 g& D" ~/ k7 {$ F
   break;7 H4 A$ G, w, F9 I5 o4 q$ D
  }, [" Y: a4 q% ^( Z, \# c
}7 p( m. @2 v+ q, b9 X; k; m
if(i)0 ~- q" U- R8 @) Y
  out&lt;&lt;"Yes"&lt;&lt;endl;5 q; O) J' b* ~% b
return 0;5 N* j. c, i# x, }; e
}

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