查看: 4285|回复: 6

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

字体大小: 正常放大

lynnyan

2 主题	2 听众	26 积分

升级 22.11%

该用户从未签到

电梯直达

1^#

发表于 2005-4-22 01:37 |只看该作者 |正序浏览

|招呼Ta 关注Ta

<

>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>
<

>[

游客，如果您要查看本帖隐藏内容请回复

[/hide]</P>#include <iostream>
#include <fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
class String
{
  public:
String(char *s="");
String(const String& s);
~String();
int Length() const;
int ReadString();
int Rs();
void Prefix();
void ModifiedPrefix();
int Match(int i,String& t);
  private:
char *str;
int *pre;
int size;
};
String::String(char *s)
{
size=strlen(s)+1;
str=new char[size];
if(str==0)
  throw "error";
strcpy(str,s);
pre=new int[size];
if(pre==0)
  throw "error";
}
String::String(const String& s)
{
size=s.size;
str=new char [size];
if(str==0)
  throw "error";
strcpy(str,s.str);
pre=new int [size];
if(pre==0)
  throw "error";
}
String::~String()
{
delete [] str;
delete [] pre;
}
int String:

ength() const
{
return size-1;
}
int String::ReadString()
{
char tmp[256];
if(in>>tmp)
{
  delete [] str;
  size=strlen(tmp)+1;
  str=new char [size];
  strcpy(str,tmp);
  return size-1;
}
else
  return -1;
}
int String::Rs()
{
char tmp[256],c;
int i=0;
while(in>>c)
{
  if(c!='*')
  tmp[i++]=c;
  else if(c=='*'&&i>0)
break;
}
if(i>0)
{
  delete [] str;
  size=i+1;
  str=new char[size];
  if(str==0)
throw "error";
  for(i=0;i<size-1;i++)
   str=tmp;  % {" t' G+ g4 e; ?1 K. s
  return size-1;
1 h3 x+ Z$ P- m7 V" q }
3 y2 P7 o% u7 @- s: S4 w: f9 Q else
+ c/ o/ P( ~' x- f  return -1;3 B- S2 {% I# o# Y
}
& l( z' V9 ^; s: Y" M* M6 ?void String:refix()
4 i& T$ ]( p! [! q{
( ?7 v/ t1 ]* G" U- v int m=Length();
1 l6 V0 j" y0 l# y; Q delete [] pre;
, G- L$ }$ ^* x- M* ~, x pre=new int [m+1];
4 I6 x1 r5 X3 i4 ~) Q pre[1]=0;
" d$ s- @4 }$ G$ m5 B int k=0;/ A/ Z8 S# |# S; t- b
for(int i=2;i<=m;i++)
  p1 |7 y3 d8 L. g {
+ M; K7 D. l  M( K  while((*(str+i-1)!=*(str+k))&&(k>0))% {& `- s7 J, f' Y
k=pre[k];# e" D" |" t% g" N
      if(*(str+i-1)==*(str+k))8 u: Y8 e& s7 ]& ^. O
pre=++k;
: w" b' v. ~- o$ V2 \) m else
* i: @" i, a4 E% R7 ?) n" Y/ U6 g pre=0;" q3 s4 i  I! m/ v0 W& E0 q
}
% b4 _4 j) E0 D; f  c8 w: Q}
: U( w0 I& j! p# a) P& ?8 \void String::ModifiedPrefix()4 D. N* W8 h, X( F7 d/ [8 I
{/ t0 o9 c1 y9 W5 t% K1 n  ?
int *f;
( I+ D% F$ j2 }! `7 } int m=Length();
0 b5 `0 k( v4 K; {* P f=new int[m+1];0 {+ O1 \3 e% @/ ]2 ]* E/ q" G
Prefix();8 f! |; c: K. ?$ x
for(int i=1;i<=m;i++)
$ n' X3 ]8 I- k. U1 E! q {6 ^6 I9 ]: ~1 J# a9 w7 I# X
f=pre;
6 y" i3 }; }8 {3 \( |/ [ }
, {0 }" H0 R  E4 c* K3 l/ f( A for(i=1;i<m;i++)
$ C- y2 F: Z# B$ C1 { {6 T' N0 R- b. n0 e% \% b
  int k=f;
  [$ ~8 @3 D! r4 V  E' v  if((k==0)||(*(str+i)!=*(str+k)))
/ i0 d0 h) W9 u% s$ P pre=k;4 C* l9 Q+ L7 c$ @: Q6 w, \
  else
: p. i! d2 F) ^+ }; E* c, g pre=pre[k];3 \" E4 Y: U% B' h; ?3 U
}9 B  E! E( q9 K" D8 F# K/ ]# z
delete []f;  e/ K% z6 g# F/ z* k- h
}* P+ F# L4 M8 N9 V$ Q& L# a
int String::Match(int i,String& t)" G" h1 w. w4 ^5 u
{+ W+ j- h" T1 p3 m8 Y1 |& P
int j=0;) ?/ T' s6 ^! s: c. `
int n=Length(),m=t.Length();
% J  M( V' o3 d# d6 R t.ModifiedPrefix();" W8 p8 ~6 a5 a
while((i<=n)&&(j<m))5 J+ s0 L1 a1 x* ]0 h/ A
  if(str[i-1]==t.str[j])/ h9 L6 J1 z" v. w5 `# d
  {
, b- x# Q2 P$ Q6 j5 H) x; i i++;
7 Z7 v$ f* D6 [% l/ v5 I! d j++;
! K3 V* k; q' \  R8 @2 u  }( n; s6 V8 W) a* @0 F6 N$ S
  else ! u( T  n  g$ `
if(j==0)
2 r4 k& |) F9 P! H- s1 m: _       i++;
5 w0 }* x2 `  ?4 k, L0 A7 X" ^9 B    else
( y$ D  q; ?  M j=t.pre[j];! y9 v* f; X: ]+ J' j
  if(j<m)
: S4 |4 H) V: _7 B! K6 }9 q: R return 0;; [% O) `' }5 E$ ?4 y. b
  else
( c9 J" |! B9 R( p  U return i-1;
+ u$ i9 U  V7 h7 \* C}
" E% }. p9 f) X: z  [2 Pint main()8 m4 V1 @7 {; b% d7 w- Q
{
& T# p: h1 H! ? if(in.fail())
4 K2 |% w5 G! `% I6 H; c! m# ~9 z3 d {3 p3 ]9 R2 j) Y" z: ?0 B
  cout<<"the input.txt is not exist!";6 k. q# B$ V5 M3 I
  exit(1);}
. M- E5 z' I# B: j. d int i=1;
5 V" x+ h+ v) j% ^* ~! I String s,t;/ ?6 I0 Z- B3 n
s.ReadString();* F7 U( L" k0 R% C- C% V
while(t.Rs()+1)
) L. m0 q1 j* \$ S' I {
% F  O$ T8 J( f$ I/ `  i=s.Match(i,t);
" y! j: J3 W' H! Y  if(!i)
4 k% ~6 n4 Q; d0 z$ \. h" y- l  {
4 l7 X; n7 P% @5 i    out<<"No"<<endl;( J5 c. e- a8 y3 Q: t
break;* H3 ^( F$ I' `/ {5 p. X
  }0 _4 i4 @) b! v- j% [
}( s  ^* G* R6 x) h1 \0 e: c
if(i)* v+ y4 o' x0 M& i  `4 d5 ?' m
  out<<"Yes"<<endl;
2 q. D8 O) o  s. [! k- ?% f return 0;
- x/ |+ r# z- p4 f  i}