查看: 3999|回复: 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;
* n( |4 w8 T2 q* M/ u, C8 }3 Q0 u  return size-1;
; R) [, `7 m2 \* x }3 h) c0 S* N5 m/ O, Z; R5 b
else% N5 S$ N, t& \& J5 j, ]( G
  return -1;% v& ^7 p  H5 k, _( Z
}. W* u; p9 \( R/ a1 a
void String:refix()
* _; k! |2 D9 s& m{
8 u9 E4 V9 U- X' W- V( e& T int m=Length();
8 q* @  M5 G7 y delete [] pre;0 H7 {9 M! H+ {2 V1 t& I
pre=new int [m+1];% P7 i2 e' ~4 O3 |4 P1 }+ ^
pre[1]=0;% y2 _$ u9 E/ h2 g) a! k
int k=0;+ I% b% ^: V8 P
for(int i=2;i<=m;i++)* X+ `; x( E5 }, W' a2 L8 b5 r- R9 z
{) u% k: t) o4 O! M8 h! |3 |* y' f9 e
  while((*(str+i-1)!=*(str+k))&&(k>0))& z3 J( G* ]5 r  n5 n
k=pre[k];
) y" ~1 f8 M1 t" T+ y       if(*(str+i-1)==*(str+k))5 r  S2 H, ?7 F
pre=++k;
) E0 Y* u2 ~9 ^6 S; l. r8 W! p' p else
/ T+ @' y$ d$ b8 z, R pre=0;
- N, B$ G8 I$ u0 V }3 H% K, n( T3 d
}& N5 h1 r4 _8 |
void String::ModifiedPrefix()" K1 s( q7 {% g, {
{4 [9 R) W" `4 l+ q  P- s4 N( K# R2 U
int *f;
! L, ~; s' N9 q8 n# y$ }# s) S int m=Length();8 }3 l7 b5 ]4 m" T: h1 H: P& {
f=new int[m+1];
( r( K4 d5 C# U$ v7 Q Prefix();
! _, r& P3 B! `8 o4 H' B: N for(int i=1;i<=m;i++)' u! u2 W) S2 {3 w3 M
{
; f6 c0 t- L* |2 E0 p" m f=pre;
% P" k( D3 t  ]$ [; G }  v( T4 R, K4 }9 y) @
for(i=1;i<m;i++)
  ~6 ?3 w+ E6 R/ B2 q {, W: S, V2 x2 u% W( C+ r
  int k=f;
  f8 }% c, H+ V% [; O* z  if((k==0)||(*(str+i)!=*(str+k)))
# r) ^/ w& w# `6 k  [; D. h4 I pre=k;
; o8 J: u; U( P5 G  else 7 ^, u% g" N+ I# s( Z: c& X
pre=pre[k];
! i! c  B4 o# e+ Y }& H4 {* N9 \2 u1 z- J
delete []f;1 E3 I& q: n* d- E2 z
}( }$ O$ q$ E6 M1 M0 }
int String::Match(int i,String& t)
; w5 q4 A1 |3 @# }  W( f% |3 h- O* A{
/ v6 l1 H9 @4 q. _ int j=0;
+ u3 l9 m# `  l9 R. N8 r9 g int n=Length(),m=t.Length();3 }& I+ o' U3 C( H/ q2 L8 T5 m
t.ModifiedPrefix();
: o: X  \" B- k! d% G2 c' b while((i<=n)&&(j<m))
. q; P. r: j/ X  o5 ]  if(str[i-1]==t.str[j])
2 E& ?4 M% V8 r& u0 Q8 G, p  {
$ e7 n4 z, f! `3 D i++;
; f0 \/ p5 c8 F  w' [1 L j++;
1 o8 s' _4 D, |4 F, B" q3 r* M% K/ C  }
, `1 S! w* Z& ^0 K  else " }. Y5 [+ K8 X: K7 {& n1 ^
if(j==0)5 y2 ^- D) R" e  c2 K
      i++;
: R) I/ c- B1 o! Q+ b    else
$ g1 y$ W, q" z; x) d! b; P- |2 x7 E! M j=t.pre[j];( R; }7 {* }' @/ S9 L
  if(j<m)
' }/ M7 r8 Y$ V% `3 n return 0;: u' P6 V; a* C% I( e6 L
  else
  [) v% a, C% Z" E% v return i-1;1 t/ W7 p, O5 V+ P! ]( \
}
. l* G) O" E1 i5 j/ Pint main()
/ A( J. @1 l3 g0 n{! ~" s$ d& ]- _" c' i% }. T' d
if(in.fail())1 S+ a0 w8 s( P+ g
{
* l& s( u# }' y; \; k( ~& c7 p9 W  cout<<"the input.txt is not exist!";
; R4 d2 t! z$ h  exit(1);}- f- k( S/ r5 X$ s! D+ T4 r* I
int i=1;
% e1 V  [0 ]: d, w: `8 w, I String s,t;) C6 M$ ^# b" J+ X0 C
s.ReadString();4 a" T9 W% U. U3 Z) x& f  P7 c$ A8 N
while(t.Rs()+1)
2 r2 \6 j) Q8 }1 v3 G {
0 ]1 Q. ]. i' d1 l' J: R8 n' x  i=s.Match(i,t);$ E" i/ E. W6 W
  if(!i)
1 e% t4 z) I* [: o8 b# L' E! `. G  {& d( [+ O3 r9 ~  P  F
   out<<"No"<<endl;
3 x8 D7 @) a; N; T2 M2 T; E, S+ M$ ?% @ break;+ R8 @+ u/ R  N" c
  }
$ v: e8 X( v. y- e& x }
8 U& w1 K$ r5 ^5 t9 h if(i)
0 H$ w# q$ E+ l/ Q  out<<"Yes"<<endl;
) q* c3 H0 u- n2 O& k* q5 L- { return 0;% @  y' L$ F$ e5 V# s4 y" P
}