数学建模社区-数学中国

标题: 间隙字符串匹配问题（c++) [打印本页]
作者: lynnyan    时间: 2005-4-22 01:37
标题: 间隙字符串匹配问题（c++)
<>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>$ X( E% n: `1 _$ ]$ Q6 g
<>[[/hide]</P>[attach]1460[/attach]#include &lt;iostream&gt;  T4 h5 ]$ z6 o7 `
#include &lt;fstream&gt;9 u, Q  X3 g2 T& C
using namespace std;
* _! f2 r) [/ e# Qifstream in("input.txt");9 X2 c6 T  w, g3 ~: c4 e2 p
ofstream out("output.txt");: ~6 c. M. l- X7 i6 Z/ H
class String
/ V# R- \7 Y1 Y{
' l/ j9 I1 q5 f# c' O. x  public:; I" b+ }( h( v6 D3 ^
String(char *s="");
! N/ C2 }* @$ i! {. i String(const String&amp; s);' H+ \* Q9 e9 S4 i2 ]# T+ N& R
~String();, }# r  t$ ]" Y- Z
int Length() const;, d7 I2 H3 t2 @
int ReadString();
1 Q0 @) K, |: y: S( G% L int Rs();: g9 e' U( Q" J1 j; z
void Prefix();) u, U% }: q- d
void ModifiedPrefix();9 i1 K  V1 H! k8 O+ X" \
int Match(int i,String&amp; t);
" U+ t* B/ p9 x; P- w/ q  private:
7 ?$ P' C6 i* v+ D   char *str;3 u8 ^* r2 P0 G+ c! e/ y8 w" N6 q
   int *pre;
  A! S8 s8 ~# H4 i   int size;
% j2 b, m, o5 L5 H};& ?# Q" I/ v! s. p& o+ w
String::String(char *s): O5 e: g: t5 h
{; E3 b7 f2 e# |0 o; |
size=strlen(s)+1;
, G' O$ L7 J, I str=new char[size];
+ K9 n6 u. _( H% Z' ] if(str==0)# N  f5 x. i+ m( m6 R  V, n
  throw "error";
# M" c2 L( H+ {/ V strcpy(str,s);
7 R  X" W# z* `& L pre=new int[size];
8 e# @  _: T1 X4 ~ if(pre==0)
& W( E, T& |# h3 _) ?" n. H9 U" m5 ~  throw "error";
/ h; M% V2 c8 Q% _1 b2 I}
) S  l8 p& I5 c2 NString::String(const String&amp; s)7 y0 r2 p: Q/ g3 x4 I; Z+ Q. h3 w
{
. E# t$ A. I* e( f' |: w size=s.size;( I' K3 p; Q2 i0 M' j! I
str=new char [size];9 N  k0 b3 W4 v
if(str==0)
' V* \7 K2 i! B4 }4 h  throw "error";
2 }# W# d7 r+ S% `6 `5 U strcpy(str,s.str);: ?$ S: j& I( z: O, p
pre=new int [size];
" D: {; l, ^1 L( H9 a6 R if(pre==0)
0 \, p: G* [' h, v! ~$ u8 i4 S, c  throw "error";+ O# V) _/ [2 d! e0 r
}2 V0 F  B- S, Q$ H
String::~String()
- q/ r& Q" \/ D8 K8 P: w{
3 |  {6 {* p5 U% X0 q# P delete [] str;
# Q. G! o8 P) T1 h) r delete [] pre;  v" F7 c6 R  k  v( ^
}
# Q# P. J7 J8 E/ K) c# vint String:ength() const/ r6 w; C' k4 h/ Q
{, K. r& U1 l  J( P4 T# c
return size-1;
& m. d$ x8 P, I, h}! K/ S* e' y/ g) L6 ]& t
int String::ReadString()* m# U9 u4 a, z% u8 `; M' J
{% p$ l% a7 B) w
char tmp[256];
" R3 ?2 [: r" U8 X% e% P( a7 G    if(in&gt;&gt;tmp)% ^5 U- l: U: s" k) K
{
; S" ^7 A' o: {6 j5 Z  delete [] str;0 D- T( Z. a; U: s5 v6 W
  size=strlen(tmp)+1;% F; p" ?$ r) j  l) q
  str=new char [size];
, H9 d) }$ \( N' N7 n  strcpy(str,tmp);4 J' S8 o3 Q4 T
  return size-1;* u  p8 s0 o0 V6 j. Q1 S
}8 f' B& |% U! o4 R6 [6 U
else
, q$ n7 ~# j7 P- S  S  E5 k  return -1;; b- V" Z. W/ U% [0 L1 X, a
}
, N8 J+ o0 u9 N2 cint String::Rs()
, ?6 x# M7 \* j, g6 p9 q{
; `+ Q* i8 x  v: E4 j. c. L char tmp[256],c;: y* l7 G* F' U, b
int i=0;9 e& L( S* P* N/ ?
while(in&gt;&gt;c)1 V3 U& W2 F/ v9 F
{4 l3 I! d3 f+ j* w" ~; j* h, f- \* E( ~
  if(c!='*'); A5 M( m5 l! z: ^, n1 r6 j
  tmp[i++]=c;* K/ P) f1 ^3 O( J/ i
  else if(c=='*'&amp;&amp;i&gt;0)
- i: }8 I$ K3 I# s3 t6 s: K" P* U5 w   break;
/ b% r0 h+ l8 E/ l( i+ k7 Z- q1 }0 [ }
( x9 q% A: \5 {9 F5 Y if(i&gt;0), d: R% ^8 w; E* q2 _
{, h! R5 l% O$ t: i8 Z# d
  delete [] str;
8 w& Z* r! v% V, D: S+ ?( }  size=i+1;
9 v9 a; ~1 K; l, ^+ q$ N0 U  str=new char[size];
% s" m* `% [3 c+ t0 E, o  if(str==0)
- Y9 M/ m" p2 n7 p: j: @- q   throw "error";
& k9 t6 b9 Y) X! G' B  for(i=0;i&lt;size-1;i++)8 Q: D3 i$ V) S, ~" b% o  }! C7 _& j% n
      str=tmp;  7 C1 b" F) _- [9 g( M
  return size-1;3 G) F6 q1 u+ b# S( d# [
}
9 D1 o, F& ?& {  y0 L7 n else$ k6 E, D& B7 `9 @
  return -1;
5 ]' F5 O1 i2 E5 l9 r7 H}6 x( ^% B! x0 B7 B& e
void String:refix()
  C: i4 X+ r; B; d# ^8 I{
6 D; z. H5 ^4 u) ^3 ?  @5 H% C3 F1 r int m=Length();
/ |7 `8 F- s$ @/ X) ]7 v& { delete [] pre;+ _) B# H: F1 O' z( g& m
pre=new int [m+1];( N5 c' _) x" k, v8 j) J0 G
pre[1]=0;
% G& w0 V9 `" n3 ` int k=0;
" {) M8 U' s* o: v3 e' B+ c for(int i=2;i&lt;=m;i++)9 p. j( {! ^  z- f$ Y2 m
{! W4 x8 U) |) r' G+ M8 k* Z
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
  A" F' H3 e$ D' [   k=pre[k];7 O) }2 {3 M' h2 O! J/ o, Q
         if(*(str+i-1)==*(str+k))
9 E9 m7 j* A" Z5 b5 k    pre=++k;
  J8 b9 E& \; Z4 z$ N   else4 v1 ]$ O- [* L
    pre=0;
8 F9 e% R, X- C( g: J  u! |/ b }$ ~) C/ ]7 k) Y& i7 |& F! K
}
7 F% V3 y& E# [& [) vvoid String::ModifiedPrefix()
  Y& C1 m3 i' Y{
/ X3 x  z8 \: g$ T4 N int *f;" @  O* ?7 b6 `' [* X" i1 V
int m=Length();
) Q9 r: C: [8 m8 g. h  C- _ f=new int[m+1];
) ~; {, l, u/ t6 x7 w Prefix();; x' u8 y4 F2 R$ m
for(int i=1;i&lt;=m;i++)
3 t  k1 I1 e7 ^: e- ^/ ^- ` {
& }% F/ U% X" Z4 A. l. P    f=pre;
; r8 b+ F( e5 U% ~/ j }2 C# A+ Y7 x: r" w
for(i=1;i&lt;m;i++)
4 ^; ?! Q$ a3 r {
, P3 ?0 }3 d3 i4 T  int k=f;
( r2 M  b5 D* C: Z  if((k==0)||(*(str+i)!=*(str+k)))
& r8 W+ n0 S6 _9 w/ s   pre=k;
: ?& e& G- U; W1 y6 v  else
$ z8 o" s5 W1 h   pre=pre[k];0 |  P: V8 \% b6 J" C- j% u" Q+ [
}0 k: i: V* I- o6 R- N
delete []f;1 V5 R1 L# `& C1 E0 v
}
+ e) f0 G2 ]2 D  z2 m$ mint String::Match(int i,String&amp; t)
) V  c9 ~0 J+ R; X1 |, V{; H1 M  {- F5 L7 w# \2 Z- J4 _+ D, N
int j=0;
$ J/ z  I/ Z' q* s int n=Length(),m=t.Length();$ E- z. O) m% s$ E
t.ModifiedPrefix();
: u9 a% p! k4 p4 j while((i&lt;=n)&amp;&amp;(j&lt;m))
( ]& c9 ^4 p/ d  {7 m  if(str[i-1]==t.str[j])) H% {+ D: R" g) D) C' z5 g
  {5 y) x3 r  R% m. i% b
   i++;
' g' J0 z1 U0 \0 ~   j++;7 N# @$ F9 K0 E# N, A8 _9 M) w6 M
  }
" p) h: Z5 P2 ~! a6 |  else
/ L- ?2 p6 v, M; z' m   if(j==0): n" P6 V: m6 N- @3 W' W, _# u3 ^
        i++;5 q& Q  H0 i: Q/ _. C
      else
& V: O: B! Z5 h8 x. @7 i4 T: F    j=t.pre[j];7 L! Q* l( C7 A4 ^  y
  if(j&lt;m)
0 F- P+ W* o6 Q( Z   return 0;
. D4 v* Q* D1 V/ i! d# w$ K, h) Y  else
& \0 }' o) \1 f; k: }! J6 F   return i-1;
/ [3 |3 |( U9 |/ |, J: y}
, M- s) K2 o4 r( U. uint main()
' @4 R. d; w% C& K' @{
7 p( Z  z, O+ Q2 U( Z5 Y6 y4 r: z1 O if(in.fail())8 ^1 V9 X% v, M/ \! _$ D
{
/ b) b3 b7 V9 t0 D2 |% ~  cout&lt;&lt;"the input.txt is not exist!";
( q; ]6 O) @% L/ t: ?  exit(1);}
# I/ x0 v- [" z& `0 p, ?) t int i=1;
: c; n! |, h- v; K% ~, z; H String s,t;
) X. X  G+ ?( ~- ` s.ReadString();, v. g* N" A3 R4 X0 o
while(t.Rs()+1)
1 c! L# v/ H$ i. @. w1 J" C {
# d3 e. \" }: n" W" l# c  i=s.Match(i,t);
4 C6 C2 o% [9 T9 O0 ?  if(!i)$ h. w4 H; I. p. ]8 g! k2 {
  {
2 j$ S$ Q6 k( o, u      out&lt;&lt;"No"&lt;&lt;endl;% C1 G5 }- c3 T9 t) Z* s
   break;
+ f7 k6 S! K" c( w$ H$ G3 [' p1 _  }2 R; ~& [5 P9 F3 f, f" ^- H! ]
}3 C7 d5 [# E( s) I4 c% c$ p2 _6 P$ H
if(i)
6 K/ U+ |+ T8 z% ?- R, j0 U* D$ @  out&lt;&lt;"Yes"&lt;&lt;endl;
* f; ^9 [$ X# K9 M) a1 d  c* @4 {. x9 F$ j return 0;) u9 }" m$ j7 b, F" j2 K+ E' @4 ^
}

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