查看: 4284|回复: 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;
+ C8 f2 o- T( \) B8 x  [  return size-1;
" u% `  Z" ^' F( m4 } }; `1 R! j/ m" y  W2 k  }
else
4 b, d5 H! M' _" `$ B  return -1;" S4 f: d; B# K8 S
}
3 Y+ y) X% S6 c9 K) `void String:refix()
' M* d' E% z- B5 D) r; L{
; G( j5 h9 n, x4 m# X/ g3 C' W int m=Length();
5 W# J1 Q2 ~7 |" L, j: Z delete [] pre;
* p1 `: Y2 ~$ v$ w) p+ R2 i pre=new int [m+1];
6 P/ A7 h6 J& D* z1 k. o pre[1]=0;
4 n& @% T! T) g" a" V5 h+ @ int k=0;
& [! I, q' Y- Y1 n& |, o( D for(int i=2;i<=m;i++)
' X  I: A- J, |8 E {
6 q( t% I% m) \: p  while((*(str+i-1)!=*(str+k))&&(k>0))
$ U! W( c" t$ y3 I. G k=pre[k];
* W( l# P4 a* X6 t- k% {       if(*(str+i-1)==*(str+k))
4 I" Y9 w4 I% G pre=++k;9 V/ @; P6 x+ P" f+ Y2 S2 }$ R/ g; M
else
' k% ^- _* u) U6 s pre=0;1 W) R) u$ a+ C+ c" Y* W
}6 Y. N- y  }: T% N, d
}% S8 N5 Y+ s$ X# Z2 @* b
void String::ModifiedPrefix()
' H3 B: |5 Y. f{$ N7 h5 c; ^! O7 N# `! Q/ }7 W5 {
int *f;% B  e1 S  |* ]/ i! S
int m=Length();3 h  q! D2 A9 f- z
f=new int[m+1];
" ~8 A5 c- L5 ~0 B: Z Prefix();
: w; Y2 z% Q0 i  U" L& y for(int i=1;i<=m;i++)
, L1 J' j& W5 _ {
" O6 H- G3 M; V f=pre;
- u+ P' B! u' W4 w }
% b8 Y+ @6 r; Q0 X% _, X( F for(i=1;i<m;i++)
5 y2 k* d! c0 P. Q0 z8 b, n {
- J: {$ v( f5 \' d+ K" C5 e6 W1 X+ g  int k=f;1 l1 x2 X6 `4 o, G* {4 Y( R2 J
  if((k==0)||(*(str+i)!=*(str+k)))! {/ I  s- l% H! E7 n6 f3 C
pre=k;4 y2 L- J# x% F1 j
  else
; C! m% y$ h: b  E3 I pre=pre[k];% B6 m5 `* \+ o5 B& ~
}# e% l$ V  I+ j* Z/ n, W, C; _0 N
delete []f;& i0 |% R% X+ j4 E" T9 r
}
2 J) x: U# _# U. n- cint String::Match(int i,String& t)
2 \. w7 h; c/ w, }, M) w1 M: Z{
  _: {0 h/ a" l) T9 D' S int j=0;
* K9 l6 p! Z' ^6 S( I7 V int n=Length(),m=t.Length();9 s# y' S2 j) z; i0 z
t.ModifiedPrefix();
+ f4 l  d& S6 h: W while((i<=n)&&(j<m))
0 j+ }! X9 B+ Z% X8 }( ]  if(str[i-1]==t.str[j])6 |& u1 d# t, A6 ?% o: M
  {
8 P" E+ B, e8 L i++;
7 T2 ~" S6 L& v/ [( q j++;# y3 r  K5 K' K7 f/ U: [* l
  }/ L. D1 @8 \: L1 B% K" o
  else
: _' [+ K9 m, B. S: f& Q2 l if(j==0)8 ]2 A8 n  D: l2 m8 N( G$ `+ g
      i++;$ z) N8 ]! @2 k6 p% P
   else
" O6 C  p% `7 h% p1 l% w/ ^3 l. F j=t.pre[j];+ t$ @/ X, m* \/ y
  if(j<m)
$ I* o. c& }. }# u( o return 0;
8 m% G. f; s: Z5 a  else 2 W) B! s6 e0 r8 Y7 i1 F
return i-1;
  g) C& G: I* ]8 F( o}
" C# U( J  _1 K' q+ Oint main()4 f6 l* }& |5 F8 X1 I+ t& E
{
7 O0 A! |4 g' I0 B( w1 s. m" [ if(in.fail())4 r3 z1 {% K$ k1 n. K0 p% ^
{; h* l. t& z3 ~% m
  cout<<"the input.txt is not exist!";1 r6 U8 H& r' V- a$ L- t
  exit(1);}
/ [+ S- \$ R9 G3 r int i=1;4 {0 h8 Y0 \# \" `
String s,t;
* e) D. g" [' l. b" D2 o' n9 N s.ReadString();
( U0 n4 k% t( R5 F while(t.Rs()+1)! i2 W- k; E. @$ F$ Z1 G( Q8 o; Y
{& _+ Q; {1 ~3 M! ~6 y
  i=s.Match(i,t);
! }& s% }# X  |7 C( Q  if(!i)
8 R7 A5 ^$ K3 u/ H( Z- R  {. s6 r+ s4 X3 p
   out<<"No"<<endl;
9 ]' A+ s" L1 I. i, \! G3 H break;8 V2 p5 I: }8 {0 z# o: n& f1 R
  }
  d; ?0 i: ?1 T' N" Z% H6 U }! n5 B1 z( q; H+ Y: h1 p
if(i)+ M% q8 i; E. b6 |2 F
  out<<"Yes"<<endl;
; T& V  O( H& Q4 g! ]) p return 0;
# {5 f( W' u6 U  \, w}