查看: 4192|回复: 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;  , L! ]5 B4 Q, y: V) q/ M9 `
  return size-1;
- A) L8 H' V. v" r! f1 a  F& i }
6 {7 h+ g. s! a( l7 V4 y else
- Q& K+ s: d7 p0 k  return -1;: i0 S# W. I9 \3 w& P+ \% z: I) E! r
}
! O. |. _) Y) j! f: {+ _void String:refix()
6 B2 I4 ~8 s  t/ w/ H. b{
* v1 O1 S% D4 n' a6 w, g0 k int m=Length();: X9 @$ w  [0 W
delete [] pre;" Q% b6 |5 U) D* u$ }# Z6 h
pre=new int [m+1];
; q; ?, |2 F* q$ i* l3 Q pre[1]=0;
: z% ?0 r! ]! j* U) H6 L' J int k=0;. f4 I2 F) M1 l* a" X# w+ [
for(int i=2;i<=m;i++)( H' A# p) H, p+ n! n# ^0 q! C
{
* \) ]# Y) B/ R, p: j& p" I  while((*(str+i-1)!=*(str+k))&&(k>0))
1 [/ {6 k! `& A+ K7 |( s7 J, P k=pre[k];$ h6 h/ c% h# p  u; T
      if(*(str+i-1)==*(str+k))9 L& ]+ `1 `; E. |5 m- _; ]
pre=++k;9 c. D# t2 ~( ]6 ~: s  w, S
else$ E- f1 C5 I2 v- h
pre=0;4 d. l2 x" q. K) e4 c& }: Z
}  Z. n% G% Q$ ~( Z1 Y; u
}8 K: ~( p1 g3 M  X
void String::ModifiedPrefix()8 o" t. D4 Q9 C( o! I3 {# ?
{
: P2 R6 C. H" O$ J6 x) y+ E6 z int *f;/ R% O6 z- T/ R$ D( Y/ F" N
int m=Length();, i, Y! L. S# G3 ^/ a" R; w
f=new int[m+1];& q* g" y6 u2 G! _
Prefix();( G, O! q# k! F+ I: e$ Z
for(int i=1;i<=m;i++)! _. x& w8 [3 C9 I& j5 w& z
{
7 m! e4 c! p4 Z3 J8 i f=pre;
$ ?# @& ~( ~5 r+ h0 X! `9 z6 L }
) ^4 d( Q  e5 G% f for(i=1;i<m;i++)
5 I$ g  i( |: y. p4 j* C4 q {$ I8 g9 ]0 b8 a! O" j  W" K
  int k=f;
: u* h! Z1 y0 {5 B2 ?& E  if((k==0)||(*(str+i)!=*(str+k)))) n) }5 G5 o( L9 y7 m! Z
pre=k;: J1 l4 ^3 T# |9 r* A8 t1 l# I4 B/ e
  else
3 z, G" _% a. f* J" ^9 w pre=pre[k];& Z2 _: L9 T  Z2 N' v: [
}
; S* d( y4 Z7 s( G9 ?' N5 v delete []f;
! B5 ]! o+ r# L4 `( B) j! s}
- |4 `- p% J# Z( p9 L* ]8 k3 Dint String::Match(int i,String& t)
# w1 _, `$ B0 p* t) l, t. D) }{  X4 d9 E& a$ B" E- Z3 P& o2 J/ s
int j=0;
1 M. I# ~) ^: C% V# a! Z/ m int n=Length(),m=t.Length();0 @# Q: a9 W0 l) L7 h; d% y4 t
t.ModifiedPrefix();4 e# }% l' [0 D6 F, x
while((i<=n)&&(j<m))! O5 N! L; H" i0 I2 l: W
  if(str[i-1]==t.str[j])2 c- |$ p7 [5 n8 b1 x( S0 z* M
  {
2 X5 L4 A; l: T i++;
% X. k% k, M2 d: A/ |" T0 d j++;
/ ]/ m2 q: K$ ~( k* @- C+ m- a4 t! a  }& n# p4 \" e2 J* o0 `
  else 1 Y  H! u5 J- M# z9 K$ g
if(j==0). x  T4 F7 |3 G4 T/ Q0 ^6 A0 O
      i++;% \( ^$ U$ S) I: I0 O& g# F, e
   else + o- d  t1 }" Z( F
j=t.pre[j];+ M$ I( Z" {8 H4 N5 ^! w
  if(j<m)6 `* }$ M/ L# I8 {& ?$ Y6 _
return 0;
9 z/ Q. {) P  o  }  else
/ ^3 ?5 H: |, G) r. {) a return i-1;
' P# b% \7 y* C; w( F. H}! o# F1 [9 y$ b4 f& E! I* l4 y
int main()
# t  Q* f* e- E1 N9 T3 c{
0 A; n1 i5 A: }; Z' g: c8 _3 V if(in.fail())! _( H+ H! }+ D- X. R# b) j, I
{
* V! |3 N, q# j3 n) J& @4 j% O: j* {  cout<<"the input.txt is not exist!";& E7 C  M1 l: J$ _, u
  exit(1);}
) N; w! I$ }5 t( I0 L3 n: h4 I int i=1;& u: U2 m8 h" \1 N  R
String s,t;
2 ?. y3 C, |0 \ s.ReadString();# i- D: y8 C" s/ g% ~
while(t.Rs()+1)2 f) [! C* i1 V* d
{4 m6 l+ Q; n2 e$ p) ?) E# w2 k
  i=s.Match(i,t);
2 n; e( }8 _* c4 E  o  if(!i)
' \8 J! d! e" d4 f" a% I. N  {1 B, s% `8 Z6 M
   out<<"No"<<endl;. [% O' U* n* G$ U7 S$ P
break;& R9 Q  {; a: C  s) I% y2 E
  }
# F+ o  f) N* F4 q9 u6 c% a }
/ v- B, V' [: A& b if(i)
. l% v6 j- ]4 j' p7 o! L- I  out<<"Yes"<<endl;
7 W  [" q2 J0 S return 0;' \: H6 r3 \5 {2 t0 f
}