查看: 4001|回复: 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;  : l6 k! m, b: o& O( ]) V9 \. z
  return size-1;
+ x) d! B- m7 N* |  O }
" F- x; ?/ z2 \5 X4 r/ i7 Z7 L else) M) y( h9 j/ Z2 e
  return -1;
! R, {+ N- ^( l5 M. x/ k  {}5 w8 l8 P7 `3 o0 C3 d# Q
void String:refix()
% q$ |' v* C' r1 I+ g, ~- L{7 F  z# F' h7 V1 ?" z4 s
int m=Length();
1 K" ]& z4 L" O delete [] pre;
8 B* @% Z3 Q" F! a* [ pre=new int [m+1];
# j/ d3 M2 G* g2 L  J  q1 W pre[1]=0;7 h' m8 B$ c7 z
int k=0;
& _6 v# r+ A- V for(int i=2;i<=m;i++)6 [. ^! ?6 }1 Q7 K5 F; y6 G8 ~
{
2 u6 w# k# ~) W$ m7 d+ Y5 z* i8 w6 U  while((*(str+i-1)!=*(str+k))&&(k>0))% G* n: t: d/ T% e( r
k=pre[k];
% f% u0 @9 P2 E& A$ ^# J$ b1 j+ {       if(*(str+i-1)==*(str+k))& Y* |0 i2 K4 N" z+ V5 R! ]3 \
pre=++k;) S1 x( |0 K, X" }0 P4 O
else, i: M4 M) l5 n, A( E+ f2 z- b+ A
pre=0;
" O) f% R5 A1 M4 Y. Q; A% C$ D }& y7 E. h, q0 ~5 p8 I9 U5 j
}5 d; X& Z4 r! {3 t7 v* @( ]
void String::ModifiedPrefix()$ n; @# }* H. j9 Y7 ]+ b% X# i
{
! `4 I- z+ J- O# M; h int *f;) e0 ^7 A; W5 V. _8 F& H0 p" Y
int m=Length();
/ h: N7 b) f8 }* R% h( Q6 _ f=new int[m+1];
* |) [! v# v$ [6 p+ e Prefix();
  c( r) [8 N, Z+ ]1 `- P for(int i=1;i<=m;i++)
' M" N, l/ C- S* p  Q2 d {
/ L; j; _2 q9 ^- C3 U# r5 p; j& D f=pre;
( b/ L7 i8 F' Q" I. H }) X; O% c) {5 |
for(i=1;i<m;i++)
, E6 m: w" v' Y& j. K* z {: T3 g3 v4 l1 q( g! x
  int k=f;1 j# P  O; l& Q/ \: I
  if((k==0)||(*(str+i)!=*(str+k)))% Y, v: y6 b4 s0 O6 W
pre=k;
$ ]  y6 L) W/ C8 u( P  else   c% D! S/ G: V% l3 X
pre=pre[k];
% ^  o. ?1 G2 A0 x, {8 P* o' q }
. D% v* a& o) n) p7 G delete []f;
5 d' J5 l8 k$ e2 u3 a. ^4 _/ U" Y}4 O" I  ]) D7 x7 d2 s7 [/ S
int String::Match(int i,String& t)
$ Y  j6 }' s5 \9 I7 r2 W" ]& `{
! A# v1 f1 k2 E: J0 {$ ~ int j=0;
# z& Y9 M. a) L+ x int n=Length(),m=t.Length();) l' `; ?, T2 s' l0 w8 T7 n, I
t.ModifiedPrefix();' U; ~/ j& c( q' n- Z; e' y7 p
while((i<=n)&&(j<m))# {" ~! e; y4 M( U! v/ X5 N
  if(str[i-1]==t.str[j])
! j: m0 f! P' d1 H9 o7 p$ m  {
; q+ x" D: w( c& i! D! y8 u i++;" V, ?7 ~  m* J3 J
j++;5 a' n6 `  Q. J$ c$ Z! L5 o& J
  }% y" D+ j' N' e$ y7 u
  else
4 E5 o& T. A/ m7 w if(j==0)" b# A$ ^4 Y. s  o# f0 i7 A/ E% p
      i++;. V! B/ L1 x, M4 G! P; V
   else
8 d+ r0 r3 {" {. E- Q$ B& z3 y* m j=t.pre[j];
! q) Y* A- v( Z. `; O6 J  if(j<m)# v7 g/ \; A9 s7 q2 f& ~8 f
return 0;: ?$ A0 K. M8 b! Q; w. o
  else
2 ?' G+ G7 i8 D' M" H% n9 b/ n return i-1;
5 q' D: Z( x; L}
0 @+ t  ~" B0 _+ w) e" Jint main()' O0 H$ [- T& d: B, G7 A) a' M, Q
{
) G2 B% L6 i; N# y# L) D/ l; o if(in.fail())2 ^, R# d" N& F' r7 h
{- i5 M; a5 {. q5 A5 R
  cout<<"the input.txt is not exist!";
) e( m+ z, G+ i$ G# Y6 r5 x% M  exit(1);}
  j0 P# U& `1 S# O* c, ~ int i=1;
1 c. K' L4 j: u2 _1 X String s,t;
) i/ ]8 Z& i$ P; F9 d9 J; B. [ s.ReadString();
0 g. I  t( S0 U* B3 L( S while(t.Rs()+1)& p- n0 D* ~- I
{* x0 H7 L7 `8 |" W5 P
  i=s.Match(i,t);' a5 y: w! ~& L. U% }. P
  if(!i)( W# C. h) A/ P! E1 Z4 |  z
  {
1 q; z& @- q. W    out<<"No"<<endl;
# e- T+ Z2 D4 a: R2 e break;6 U5 q( Q5 s  f5 O* F
  }2 A: o2 x9 T( x  g) n
}1 _, q7 k8 P" W: k
if(i)
- u+ B7 b7 E- r& j7 B8 Y0 A  out<<"Yes"<<endl;
( a% P7 q6 }1 ]+ u return 0;
% U2 {3 z, h, f1 z% }& k}