查看: 4232|回复: 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;  ) b4 i) B0 \  n6 w2 P+ B/ p; S
  return size-1;
0 [5 A. h8 p$ O+ V& S  R }  x" g- z% q# O7 [2 @( B3 o0 g5 y
else
8 o6 X4 R' T$ a: {: W3 i: z) c  return -1;0 ?# H; H& d& ?# C. f8 S% Z$ b7 \
}* l8 I9 H. V# n6 n7 U! U
void String:refix()
& `  P; |4 A8 m# m. q{1 @7 g$ u1 U% U# }5 v7 p* r( s
int m=Length();
1 @5 R; u7 S2 _ delete [] pre;4 ~; s; m% a7 ~2 Y1 A
pre=new int [m+1];; Y- ~4 C6 o# A$ ^2 K" l" Y9 [
pre[1]=0;
' k, k$ ^% c' w* C9 @6 z int k=0;
5 {' s- C: Y4 S# Z% ]  `2 }5 d for(int i=2;i<=m;i++), {( i0 a2 Z6 E+ }3 S
{
8 w9 L5 h3 f6 a& l* q  while((*(str+i-1)!=*(str+k))&&(k>0))4 C) n4 y# P  T4 x* r  d
k=pre[k];
  J+ `3 t( L& N& L8 q  O       if(*(str+i-1)==*(str+k))
2 B! ~8 A. }" s# a8 k8 o0 B pre=++k;' G5 P/ j# m9 n! n" p
else8 m$ |0 |* Z4 n
pre=0;$ G2 \+ Z0 N5 q5 n: T$ q( H
}
  T+ Y, G' D* `/ j" r+ y3 ?% z4 U" M}
7 w1 I! F; D9 F, ^void String::ModifiedPrefix(): s9 w8 l( c- w0 H2 G
{8 m' K. A% G7 P4 p$ u
int *f;
1 [' l6 f0 ]; {, y; ^) v int m=Length();
0 \- i8 L8 z! s9 L9 x5 I f=new int[m+1];
$ f$ M% |' o# |% o Prefix();% w; Y  g# G, d5 g) [4 O- G$ ~+ z
for(int i=1;i<=m;i++)9 D& P3 D* T  R) L6 u  c+ ?% K# _
{( ]% l& E* I6 s8 H# q
f=pre;
' ]4 k/ D8 g& I  U }
$ X) w7 S- R; d  w! v- O3 q+ _ for(i=1;i<m;i++)
' t) P8 ~9 D6 T4 w: e: c- E {7 g1 X+ [, m4 A9 d
  int k=f;
$ n2 ~# i% N6 V. I& a+ h% v# A5 w  if((k==0)||(*(str+i)!=*(str+k)))4 i1 m! r5 _9 n% s4 ^0 {
pre=k;2 p$ e  j- v: e: F9 Z
  else
, S! Y- Z1 L5 H0 E0 r  F pre=pre[k];
: W, a1 q1 k; L7 I }
; u8 O, s; [* \, }4 L delete []f;. w- ?0 C# ]' Q# G; J; s
}! @7 ~  _3 ~7 s) _+ S+ w
int String::Match(int i,String& t)* ~2 h) K% {; _& f- W; ?
{7 Q" f# g( d4 B, V! k  g
int j=0;0 [0 {% s& G  _# k
int n=Length(),m=t.Length();
. K0 P! y9 ~1 x: V5 Y t.ModifiedPrefix();( b" a* C2 ]% X3 @
while((i<=n)&&(j<m))
0 r4 _: ?; N: H6 z( t+ ^" _  if(str[i-1]==t.str[j])
/ e7 f' A) K* t$ b% E2 L+ R  {; R7 E, n6 x) \, z
i++;5 ?3 ?" P0 a; y9 O% b, g
j++;! I0 R) v7 F5 o& |/ f6 I5 V
  }
* R' ]$ k0 ]# \3 `: M3 g; b  else ( i' l" K; n  @* l! E5 a6 ]: j
if(j==0)! C& v! f8 p2 d: i# M' v
      i++;5 w  j5 d, e/ ~; C; O
   else
& _# i; I% C0 ]8 _ j=t.pre[j];
- @# C: N( X" V/ a4 {! S3 J. J  if(j<m)1 m5 g/ c  C: Z  v- z* \, l( @
return 0;
8 g" ]8 Q, c' E) R  else
; H" c$ t$ [3 F2 d: @ return i-1;+ W, g: l: A1 e4 j0 Y
}
2 a! b+ \) h* ~! G4 G  [int main()1 D3 o( R5 Q0 T1 U( y
{
. L$ f  ]  ^3 _. N1 L0 V if(in.fail())! Q/ K6 G, ]- ], ?2 g1 r# N6 E
{  C" b/ u9 P" B- ?& B+ e, h+ h
  cout<<"the input.txt is not exist!";
; I. l5 C+ _; p( G  L5 B  exit(1);}
9 y$ G( [2 g/ h% ~9 j- L( } int i=1;+ N! _4 V! U8 ~4 Q1 l
String s,t;. o: R2 z2 \/ m: R  X' k5 h4 n
s.ReadString();+ o) }9 K- Y7 d* {
while(t.Rs()+1)4 G- L' D: J  I# I  H0 A) V2 M
{
- b7 {4 R& ]& Z: z  i=s.Match(i,t);1 h( j/ D$ e5 \8 x
  if(!i)
, W, x# i" }$ f  {6 D8 ^8 K/ @$ h/ r% [' Q+ c
   out<<"No"<<endl;7 w  \6 q4 G6 D5 Q+ e5 ^
break;3 J! B# F0 m/ M2 U
  }8 H8 T" ^, z* x4 E
}1 d" h3 _! O3 z
if(i)3 e: i; L' u+ [$ b) _
  out<<"Yes"<<endl;* l( m4 |; l, j! I8 h
return 0;# P3 Q0 Q# u, F5 e, O) I
}