查看: 4230|回复: 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;  / U: W& q* k4 Z! s3 Q" p  m, B
  return size-1;# n1 _4 @6 _7 [. ~( M
}
7 u+ M7 V' k# }+ [ else
/ J0 K  L2 g. r- j# X3 S  return -1;
7 w( b/ ]7 g, F, G$ n$ c}% G2 u( D/ a4 }# w  ?3 L$ X
void String:refix()% e' ^: ^% x5 V( \& T1 U
{
& ~( h/ F/ S/ C' c% O" w" m5 w int m=Length();
  Y! N# C) y0 N( T2 v, n delete [] pre;
8 M& Y: s0 B. i  P6 W' N) _ pre=new int [m+1];
9 J2 m: r' a; w pre[1]=0;
- i, l0 L& T2 ?; p, j& f int k=0;
: p. M4 ^% J1 O7 X0 }& t for(int i=2;i<=m;i++)
9 r+ y/ V- c  ?+ O2 z" W2 h; m/ c {5 t) E, @/ b7 k4 w* |5 ^
  while((*(str+i-1)!=*(str+k))&&(k>0))! Y+ K  k8 B. t: H  y
k=pre[k];7 j( A2 B) K8 K- R' l
      if(*(str+i-1)==*(str+k))
1 h/ O' f5 v0 e' _9 e# B! N0 Q; [* l pre=++k;0 ^8 d+ u% P2 r* L
else
" W- ^( u* k! \/ o( g+ K pre=0;8 Y6 n0 b( i' G" G3 ^) _" Y$ W
}. [, g7 M8 [0 R0 M- }5 G  ^
}& Q) J/ g9 W! v/ f2 ^
void String::ModifiedPrefix()- b4 A; G: M1 \, f
{) }! `" H! q% u" s! r3 a- C+ P
int *f;& n1 x" G0 m7 l7 Y8 K$ D7 Y
int m=Length();
% M' v5 F! ~1 I6 q% f: Y* Q f=new int[m+1];% Q- T5 i* V, }& b
Prefix();' S6 H( N3 v9 N
for(int i=1;i<=m;i++); {" C& {! R0 \' Q* p
{4 \/ l; }  N9 {) U3 O( i$ |
f=pre;
1 m; u/ ?8 j" Y5 Q* l, u2 | }2 h1 g" Q4 l) g  v9 i4 \8 D! }
for(i=1;i<m;i++)
" e6 B; C% @2 I3 K+ \6 ] {5 @0 y* |! ^  N' y) Z
  int k=f;6 C- X& y- }7 q' g7 c0 y
  if((k==0)||(*(str+i)!=*(str+k)))
3 |$ h0 s& d5 S pre=k;
+ b3 J6 {% u( l  else . M3 v* x7 ~; E& F  i
pre=pre[k];( W6 R0 L; V  ^' ^2 L* ]! b; n
}
9 V* e5 B3 Z$ r) }- I+ B  i$ p" d" C delete []f;3 ~, p9 R0 K7 s  F& w
}
1 F/ X# g, p- H7 V' S: N8 D1 ^: lint String::Match(int i,String& t)* ?1 @" }/ C! _" w2 g8 I) b- {
{
7 |5 z" e  r4 C1 v int j=0;
% R. Y: t4 o  }5 B* J8 A int n=Length(),m=t.Length();7 c) ]5 B2 I* Z# s: \3 X4 a" M8 J
t.ModifiedPrefix();! p. d% A6 ^% v0 D) V# L
while((i<=n)&&(j<m))& s# b; [3 f8 Z9 F3 ?1 o! Z7 o
  if(str[i-1]==t.str[j])
4 q1 X, ~1 C+ z% T$ y9 w  {
) \' ]8 R2 N: j/ B2 G i++;
$ {$ z% E; {5 z3 w; n6 l j++;4 r. C) q& ]8 W& E0 V
  }
  V9 @4 K. g3 T# o* n  else " N% M6 b8 z8 y5 f7 j, H2 Y
if(j==0)
# S% d8 y; P$ f+ y0 g# T. ]. U       i++;
2 y% O6 t9 ]  j( A" F! K! [    else : I! p: l; j1 Q  y# [9 I
j=t.pre[j];7 R: O1 T- d6 W  ?& y
  if(j<m)
9 ]& i6 H' ^& t3 B& I0 i return 0;& K, R+ y0 Q% O& r1 K  z
  else   g4 k$ p& h( z6 p, L7 W) U
return i-1;
% L( L- K$ Y% Y2 Y3 D# ~) W}
2 \; |8 S/ |5 J. Cint main()8 h5 D/ T! r9 s0 e$ Y& z! {4 t6 c: c# e
{
4 [" }* v7 x5 Z( Z! ? if(in.fail())/ {0 _" \. J+ g# h( ^% ~
{2 B' j) B( d! X" V, i8 \+ g
  cout<<"the input.txt is not exist!";. d& _- L* ?) K& ^/ c% {4 w
  exit(1);}
' B* n% @+ c% O int i=1;3 y5 i2 Y) r8 V
String s,t;5 h* z& h% c0 g. ^2 ], p
s.ReadString();4 t% k% k& ]) ^" \( I& g
while(t.Rs()+1)
+ }8 b0 B% ~5 y. _ {
' g$ b' \, u6 Q. @. f/ a8 T  i=s.Match(i,t);
) w2 I5 D$ |. D! M/ d: ^9 q  if(!i)
1 V* A* G. W- Z  {
( |* U5 Q$ h2 C5 \( }; s    out<<"No"<<endl;
- F7 a# `+ G1 z) h2 y+ F9 n break;
  d/ f" e. H8 g1 K) t0 d* x  }. @  R3 M$ i! r: L
}- z3 S: K5 g( K, l7 x
if(i)
: r9 P$ S2 h7 C: O8 a  out<<"Yes"<<endl;: D6 ^$ R4 d! ^- L+ i  }* @9 j1 a+ L
return 0;
: U* P& E! G4 L( q4 C/ G}