查看: 4187|回复: 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;  1 {5 k$ q# J( T5 P, {
  return size-1;$ I7 e1 N- g  J- c' x9 u* l
}7 H7 u3 k" f+ n$ O' D3 t
else
1 ]/ D* y2 z5 d: u* L  return -1;$ b9 c0 t1 L# r& X
}0 o! c6 n, C3 B) P6 b
void String:refix()
7 x4 `' a. \6 L0 N( r1 }: I{
+ R5 z- ~! s% l7 ` int m=Length();& r/ r9 u3 ^2 J0 @, g% \+ ~
delete [] pre;9 k1 H3 y1 g0 Q9 v
pre=new int [m+1];; t# I, C* |- L/ a$ p
pre[1]=0;7 z  P1 t% X( d& ]$ M
int k=0;4 r  |: }3 Q" e) r6 V
for(int i=2;i<=m;i++)/ p! z' E+ P- p
{
( B, p: `+ {0 ~" [# O1 ]; y( _$ }3 X  while((*(str+i-1)!=*(str+k))&&(k>0))5 k2 S% N8 Y: z/ Z5 L' q# X& V
k=pre[k];
  S+ Y: i2 |/ m# B+ w       if(*(str+i-1)==*(str+k))' z$ d; |% \: y2 Y
pre=++k;
( {/ v: U7 z- L else
' x+ C( K# B' H! ?' H pre=0;! _! k: M, ~# f
}
4 h! u) k  o# u+ }}: S$ B; q# J9 `  k% |
void String::ModifiedPrefix()
# ]! k+ S* ^. E) m5 M; y3 W{8 R. D. U( S( {) P
int *f;6 w) n5 Y; E7 J; K# o- c! n& m, |+ A
int m=Length();
0 [! n9 S( T/ u f=new int[m+1];
/ [% Y2 ~0 Y' `9 }2 [6 P Prefix();! g7 P. L0 L$ g& y
for(int i=1;i<=m;i++)
/ ]0 B3 z& q. F8 d {
7 P2 X  a0 U0 c. l f=pre;
$ M$ m6 x$ D  I  h }8 q$ }0 }" N5 l" D
for(i=1;i<m;i++)' }( j: z5 Q( I: U) {
{9 M9 V% u' v3 W5 h. x* l! t  h
  int k=f;
! }5 z" k+ A" F' p) [  if((k==0)||(*(str+i)!=*(str+k)))
$ \. Q* e' X+ A2 z" N pre=k;% z1 N/ m9 _$ K& H& t
  else
" ^9 W2 [7 z5 S  Z. Y; i pre=pre[k];7 j* Q4 p! @5 b
}
" \8 |( K% N1 D$ C, d2 N delete []f;
0 O: `7 t0 m' g) ]: S# J) I4 l}7 b4 U+ v( m/ Z  G
int String::Match(int i,String& t)/ w. r2 D. b* C, @0 \* n
{
, _* I8 B- D( N5 |- l# e int j=0;& _1 V( z- E% b, J
int n=Length(),m=t.Length();
, l7 O: f% s( M9 Q/ K  c, p$ r t.ModifiedPrefix();
4 Z% o7 q7 J1 L4 e+ U: x while((i<=n)&&(j<m))
; Q# ?! i( Q2 k2 h' `/ t: f  if(str[i-1]==t.str[j])" I8 ^* ?+ F6 z. C/ C) N3 z
  {- g* U8 _7 g, {5 f3 p  Q9 ~
i++;' g8 @, v8 L4 \. A# N
j++;$ P# [- U3 ^! {8 J
  }
# V4 d( ^, ?" W9 h  else 2 A. f) `1 |0 G0 z# R  U! ^- E
if(j==0)# J* G, j" p! ^! a" R
      i++;
* B. T% h% z$ j* @  h1 }, v    else
* H* Y2 ~0 {) T! H2 f' }% Y j=t.pre[j];
, N, x, _8 D( k- i$ X, u* G  if(j<m): B1 t, R- v, A# t8 c
return 0;7 K. \$ {; `8 x0 j8 K. N5 ]& _
  else 4 u+ k4 q& r1 z' B# j) W2 T! g$ i
return i-1;( F( Y  w2 C$ l, f* B2 u4 G  ]9 Y
}4 D. H: N, ?- S5 H; J
int main()
$ y, }' G) J& K" Y{( C$ F1 S( _6 U# l5 K
if(in.fail())
# v/ y* O/ m/ L1 W( Z* q {
  u, v5 E# Q( |, s+ i  cout<<"the input.txt is not exist!";- \2 X7 k$ f: p3 C& j3 e7 i, [
  exit(1);}9 F1 B- V% b% ^  `/ h
int i=1;
+ K. A, g2 Y  }' w String s,t;
4 d( J3 S, X3 b0 s+ A s.ReadString();
. E) W0 k2 w; t* K; n; c6 m while(t.Rs()+1)' y, ^5 L1 ^6 ?4 s
{$ F% ]0 \1 {: |: @6 D% n
  i=s.Match(i,t);
  U9 {+ Z2 X$ _( U2 t8 C' W  if(!i)
8 U. Z. Z) j5 W; I# _. ]" [  {
9 m; u: k- g0 T; b    out<<"No"<<endl;4 P1 h6 _: J( R$ T. D
break;
3 |+ }0 M0 L% I+ M& w  }
7 I$ {4 j1 Q8 g }
( b0 `# e4 ~( L3 L if(i), P, u$ a( c9 J1 N! ^
  out<<"Yes"<<endl;: v7 A3 N5 b1 w% n* x
return 0;
# R$ o- _7 A. H, F( w0 }}