查看: 4186|回复: 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;
, p* k/ O/ F& u7 j  return size-1;7 @! d2 n! g/ Z! K$ u; A% S/ o
}
! T- b$ Z1 s  S7 O else' Y$ ^1 m% A/ O: d* x: w
  return -1;0 D8 a4 }9 g% @
}8 C1 J9 T8 E, n4 m3 y9 e
void String:refix()
! [. x# }1 a. f2 a{
( f3 Q( _  @- H9 U* \ int m=Length();
; X' {8 O/ ^' A9 {7 \; L delete [] pre;4 c0 E: x- S; B* ^, s2 k, M* x5 O) ]
pre=new int [m+1];
% u) V; b, x6 e. d# f( ] pre[1]=0;0 D3 q# W( G- F* M
int k=0;" {1 m) ^4 `: j& {- o9 f: U7 b
for(int i=2;i<=m;i++)
1 y1 Q+ }% H& f1 w& e {
; U% q* I! p4 ~% l  while((*(str+i-1)!=*(str+k))&&(k>0)): o& V/ @* s" n' |
k=pre[k];# h7 e2 T. }4 t
      if(*(str+i-1)==*(str+k))
- ]+ X" P5 T: J. v  y( Y pre=++k;, \2 P, i# f( p# Y/ I/ x, Z
else
( b9 i) E- ^2 V; h2 r4 b pre=0;
1 x$ \$ o$ Z, ^  _. D  p% g. Z }
) O( r+ _# d$ e9 r8 D8 g8 N}
! B: j2 n; L; c6 mvoid String::ModifiedPrefix()1 g) N7 J' }' N2 w/ l
{7 @/ e4 H( L1 o3 S5 ^
int *f;
, M  B' E3 F' h& V3 L int m=Length();: X! S. j( ?8 B& J% g7 N
f=new int[m+1];
5 a/ R1 B2 O! N6 { Prefix();6 P* M$ N1 X' j
for(int i=1;i<=m;i++)0 c* i/ v" U& L0 Q
{: [5 S" j3 \- g+ `( G( ~+ i( ?
f=pre;
! w3 N- |# I* \; U* ^ }
, E" e; Z; M8 g. e for(i=1;i<m;i++)1 Q9 F- T4 B3 e9 B
{5 X5 t/ d& h& m& F0 D1 ]6 {
  int k=f;
& E1 X( P8 L4 T* ^1 E  if((k==0)||(*(str+i)!=*(str+k)))! w$ ~9 l/ |1 d3 I* N
pre=k;, h4 @" ^( K2 J: O! H
  else # m" `" V$ ^: g! g/ Q: w+ ?
pre=pre[k];
. r- D0 e& `2 X3 L, v6 b }
7 r9 u. z9 K. [/ h2 @" f* W( g9 w delete []f;
* Q7 N, q/ m6 V! w: J}4 j, u6 Y4 d- q* K4 V3 g
int String::Match(int i,String& t)
% }: j6 Q. q5 S{
& s8 d' C( P, M2 U int j=0;! I2 B4 E) G" ?4 ]
int n=Length(),m=t.Length();
8 q0 j! r' \0 N0 \4 Y  } t.ModifiedPrefix();, N+ g5 S* t7 f: F+ d- p3 F
while((i<=n)&&(j<m))
: k. W' G* Q' b, X+ g, x  if(str[i-1]==t.str[j])+ I, h  C3 {* `$ V( P
  {4 X8 C& [: J( t9 d  g3 W* Q
i++;
- G$ T- J$ }. L$ A3 O j++;
- N3 ^: [7 S2 z) s9 R% K' s5 M  }
0 P5 z$ g( _- W* P% W  else + n/ _# j; y. c+ D" `" O' |
if(j==0)
) [# j5 F0 ^& Q       i++;- ^1 e4 F+ u  g) I3 q! [$ ], M
   else , m1 S1 o1 c' i1 O) b
j=t.pre[j];( [8 v7 `( P% [3 N- J$ d
  if(j<m)
1 ?9 G( Z/ ]  G. V% z' a+ J, m: O return 0;
% [* e7 U! E9 o. ~7 ?  else 5 F. C/ R% Q: S, k0 g
return i-1;0 {  D- q' s# H& Z3 f! d
}
& V4 u+ Q7 Y3 {7 v) }int main()
- j2 Y$ g( H6 g# ]6 O7 z; _{
& P- h% I$ n& q) ~8 I) e7 C* u; y if(in.fail())1 _7 X5 _8 j* Y  j( N
{6 S7 Q6 S! U% b. _7 P. e* H
  cout<<"the input.txt is not exist!";$ g  c  i: B5 h1 O, [. l" }
  exit(1);}
9 u; d1 @- ?' Z9 a int i=1;/ E0 E& K# [, V/ w8 J/ J
String s,t;, e2 K4 b( i9 }
s.ReadString();
( T1 b. `& R8 |; }: T/ ^1 r5 `5 X while(t.Rs()+1)+ r9 E1 q: |1 {. ]
{
5 U  O5 Y. e% C- H  i=s.Match(i,t);5 n  ]1 S, i' K  g2 X/ j6 [
  if(!i)
  {% p1 N8 i# K2 P# A0 Z
   out<<"No"<<endl;& h1 N+ `- j6 @" }4 d/ P% {
break;7 p; F1 S2 r: o) s4 g. _
  }
/ A' c8 [; c. { }
; p* Y& h! S* g+ O if(i)* \% z/ B' k# w# g) @5 ?
  out<<"Yes"<<endl;
' p' I7 Q2 g# @; Z" o$ X! ? return 0;$ V6 v: c+ n& V
}