查看: 3990|回复: 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;
- ?" t: t& [& T$ s" P8 K" o2 r  return size-1;. c) E  x4 n6 Q
}
% _3 y+ g: V0 Y7 i1 {. g else
( [) L$ a& y) [$ M) |% L3 r0 Q% q  return -1;' I1 |5 D0 ^) f' Y: r0 {2 x
}2 D4 s3 P5 x5 y/ {  m4 e; j, `2 _9 i
void String:refix()8 Y, w2 U8 l! L# P7 o4 T: t
{2 _9 ~) }3 H$ ]+ R, X# P
int m=Length();
; y1 G3 G: I' |2 F& n4 |+ n delete [] pre;
, J7 _7 O: v( \/ Z1 ^6 L6 z pre=new int [m+1];
5 u) l; \. T; O3 E1 s pre[1]=0;
) b5 W5 \4 u  @ int k=0;
$ K- ?/ S; g5 E) b0 j for(int i=2;i<=m;i++)
  a- I' Z0 v" b  s& q  g9 s {1 b- o0 P: h! ?
  while((*(str+i-1)!=*(str+k))&&(k>0))0 b) B0 T3 `0 y/ I7 v$ w7 Z
k=pre[k];
; j9 u& o1 t* b9 s       if(*(str+i-1)==*(str+k))$ w) d; o# ?$ \3 L
pre=++k;
, V" z4 ?9 l% c0 h0 [& Y6 U0 l else  W: w5 F, N( p& d' N5 d
pre=0;9 Q* A8 A! [! E* X( l* {
}/ w  d. n) C8 Z! ]4 v# d7 Y
}
  _* v' q# ], ?void String::ModifiedPrefix()( D( ?5 c+ W6 r3 H/ o$ w
{# F0 k' i& Q8 I, V$ B9 j2 W
int *f;
+ f+ E" }% t' w& L8 y int m=Length();
- |0 Z- r. Q' l0 l- u2 Q f=new int[m+1];
: `# ^/ y5 p' X' [# f  ^: R Prefix();
2 g4 Q% x7 Y- B; e5 Z6 q. D" @ for(int i=1;i<=m;i++)  X- E4 [$ ~8 @& |  j
{
- L0 s# K3 R! W; F f=pre;
2 O( ^4 r! S4 L) S' N }8 c: ^6 H0 P6 q; ]4 w4 f$ e
for(i=1;i<m;i++)
! ~7 E+ j" r( ^ {
% h0 u% G, r2 r. L  int k=f;
1 Z- N6 p% P- H5 S- b  if((k==0)||(*(str+i)!=*(str+k)))
* |! P* g! D9 i+ ]5 v pre=k;# A( \1 n. f4 G' h
  else
pre=pre[k];
: K8 e5 ~9 o. e; i }
' r! u, X0 x1 Z0 M1 {* | delete []f;
; ]# h+ K9 k" O1 T! c3 q}7 o5 ^; H% B! J# _# N. g* l: y& S
int String::Match(int i,String& t)
* z( |7 m* m& C3 Y& K& t{
' J+ Z& l, x5 p4 H, [$ H int j=0;
4 G2 W* T$ B0 W8 j! s* ?. S' v int n=Length(),m=t.Length();* D0 S" P) F2 P: K4 `1 z" R4 x
t.ModifiedPrefix();
( F' Z3 a1 \: a  [ while((i<=n)&&(j<m)), u7 K- a* Y8 ~$ d3 s
  if(str[i-1]==t.str[j]), ]: P: x- L5 T$ b0 @
  {
: g# Z$ x3 G0 y! Y! H i++;
5 q- ^) G/ v% s$ [( _ j++;
* n- h+ {/ G- @% R% @  }
6 C6 f( p' i4 ^  else ) c" r4 A5 u# J% w) V3 U
if(j==0)
9 V% E% `2 h3 N3 A/ k       i++;% E/ Z, n! L/ y2 w% T8 |4 I
   else
3 m) ?6 }2 v  }2 p j=t.pre[j];
. Y0 F, F2 Y8 k* W3 Y0 h2 ]  if(j<m)
' d8 c/ R, `' X4 T, @' e# C return 0;
' ^2 i; _$ j0 X" l& O, w  else
% q& Q$ ?2 }1 w, a return i-1;6 o6 h7 O. o1 b+ W* b2 W
}5 ?7 Q. b7 o1 ?; n% `! y9 m
int main()
; z  m! a1 N( T  ^3 P  O# W/ V{1 {; }6 Y% I: N" f/ }, A
if(in.fail())
8 W! ~- `3 _9 G& T {
. D# e0 {$ k% M( z2 l2 Z7 [  cout<<"the input.txt is not exist!";  G8 H% X. j' K& _2 L; U! E
  exit(1);}
0 ^  ]! d- K7 Y% N7 l4 J7 K int i=1;  w( k9 N! O3 ^1 A
String s,t;! c% C5 G2 q8 [: D; t2 _4 u
s.ReadString();
# b) `" F9 d+ t- f6 e' F while(t.Rs()+1)
' U+ U+ N! c! \) h+ f0 i {
/ |( s" ~/ k' s( Y  i=s.Match(i,t);
* c- \/ [  t2 Y. [  if(!i)8 B% E  g7 i" C/ Q2 F
  {
1 F: h9 G2 r+ Q7 ~) n! |, l" b    out<<"No"<<endl;
( }* f4 Z0 V: B, v+ B) b break;
& O! N# \7 y7 V  b4 o  }
9 V0 s0 a+ ~* h; E0 G }- f  ^+ I( c, M. z8 J# t/ k
if(i)6 ~" E0 u, @- N/ N0 h0 {
  out<<"Yes"<<endl;
; U' l2 ?# K' v, l# p. j/ _ return 0;; _5 Z3 ^3 Y& Z; x3 k
}