查看: 4190|回复: 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;  * E+ [# r  ~2 f8 [- `! X
  return size-1;5 {' ?( Y8 |% I1 }! b5 x* H
}4 |& s% y( o0 W' G0 L
else  \2 i) h( M% K  ~  P
  return -1;
/ V* y6 c8 b! O7 T5 ]9 t}
  l8 u$ Z4 z5 k/ _void String:refix()
$ J- m4 G4 h# J0 C* h8 {) q{
6 G$ {3 b) i) G/ S* W, q5 I* H+ @ int m=Length();
+ X; p0 e" k% R1 n& K# J delete [] pre;
. \$ l- Q6 v6 L* o; Y% |  t# h pre=new int [m+1];6 u- q2 s' H9 K& k! u9 L$ N
pre[1]=0;8 ^. X. G1 r1 [$ a5 ~
int k=0;. s0 r8 T" n/ }8 \( c0 g* G
for(int i=2;i<=m;i++)2 p$ A; D( F2 p8 c) b1 s# w5 W6 Y
{2 U. P# Y0 A- W- j4 l, \
  while((*(str+i-1)!=*(str+k))&&(k>0))
, o/ }( h/ ]' ~, Q/ c" M$ o, E k=pre[k];- [# a  @2 A  }) P0 q, B
      if(*(str+i-1)==*(str+k))
: F; {* p; p  f pre=++k;
- o  q7 O' E5 M. q& _ else6 ?6 Q# {2 l( g$ O
pre=0;4 b0 A" B# }. s
}
+ s. L! d8 [' ~% d* i2 U: i}/ O) N8 f1 ?! U0 o0 t
void String::ModifiedPrefix()% W6 F- x3 h+ V* Y/ O7 o
{
1 I' H+ O2 Q; w* a( V7 n% S! W9 S int *f;
  E6 M8 b( h, f0 ^3 E9 H" V int m=Length();
# t# N; b, p  b+ O f=new int[m+1];
* B6 Y/ t, C. e# d; h) Y' e4 x Prefix();
( X! a! y5 x0 R for(int i=1;i<=m;i++)$ n3 d8 L9 Z% E5 R
{. T# y; o" J& c+ |6 U+ O
f=pre;# q: A3 E/ `/ D/ k) V
}
- L! `8 T4 |3 O& `8 _2 C for(i=1;i<m;i++)
' N) S- P6 a6 Q4 l$ a( V' e {
, \" W9 Q2 |  N  int k=f;
- C1 X7 V6 j. \6 x  if((k==0)||(*(str+i)!=*(str+k)))
& x& p! ~% U! Q9 T3 N pre=k;3 I- i# r- N9 }1 y# J5 b! _
  else 9 I7 y- d9 s2 N. n
pre=pre[k];
" H1 F4 P' a$ V }
2 b. m3 E+ X, G7 v7 _/ G5 s' N delete []f;0 Z0 C% N, U; l- W
}8 }2 W! |- H$ s/ y" P
int String::Match(int i,String& t)* A4 ~5 ?: B6 j$ @" U* L
{. M7 q! t8 s8 _9 u  i
int j=0;/ r3 s, N* _  x( ]- d3 ]) D
int n=Length(),m=t.Length();8 i+ \1 s9 u& S" @  N. C# x% z
t.ModifiedPrefix();0 n2 a! C  w! f
while((i<=n)&&(j<m))
+ ?& K0 e+ S/ H, P  G2 J; a/ y1 U. K  if(str[i-1]==t.str[j])* E) x" B8 a& O) t' y% `6 S$ z( o
  {- I) X! Q3 I0 R1 O4 r- N4 W. P
i++;
' I' `" F$ w9 p& |3 H j++;$ ]$ a8 U1 Z; L- `/ n2 F
  }3 y0 k% Z! A; G. ^
  else # J2 a4 v/ l1 T9 U* i
if(j==0)( [2 \4 G  G* j- y
      i++;
" K' K2 p+ {' }1 |! }" Y2 C    else
2 W) K* F$ z/ L4 T1 P j=t.pre[j];
+ D5 {- w( R# M# g  if(j<m)0 b' b' a6 ~& ^0 j. N8 F
return 0;
# e8 J0 v% B; x/ _- Y  else ) r6 i, X$ a/ m9 W' h% Q
return i-1;
0 W8 n8 H, Y* P5 @4 S  U}
; a5 }5 y1 @' {+ v+ m+ d; `int main()
5 e+ X8 R) @  g{& F5 a( g2 y& G2 G4 d& F
if(in.fail())
% z7 I, A9 S1 \3 [ {* l" \# g7 D  @' I9 U* ]- g
  cout<<"the input.txt is not exist!";) W) _0 X+ V0 W& L1 V' J( i
  exit(1);}  ~  m2 I4 a# A& e& D2 u! S
int i=1;" p- Z; a' V3 v0 z) x; t9 x- }. }
String s,t;- _7 i1 d5 @, {( U8 Y* z. j2 A
s.ReadString();
& m1 ~2 w; v6 H9 D: M while(t.Rs()+1)& ?9 d" Q1 j6 I
{4 M7 W) W- T, `2 [: y2 y
  i=s.Match(i,t);8 w# _* y6 o# k$ b+ n/ v% Y
  if(!i)
& Y5 H, `, l% w2 V8 C6 S% t1 s  {0 p. ^, M4 }0 z
   out<<"No"<<endl;
3 b1 b, I% ^/ K/ y5 [" y6 K3 n0 m1 R break;+ ?( W  o* e3 k. S% z5 e% [
  }
7 @* u, T* f4 X9 F) [ }
0 @3 A9 J8 q) O& \. w) V if(i)/ m4 m7 Y) t& A1 C
  out<<"Yes"<<endl;
, h: N6 V# C$ f7 j return 0;
! U( q- a3 g9 J% a5 |: K2 a) M/ ~}