查看: 3987|回复: 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;  9 q% m6 A0 M* g* @$ e9 M
  return size-1;
. J; `- L2 ]4 \" q! a }. q  @. c7 l/ o8 k+ G
else
/ d8 k  ^2 s1 s- A  O) u  M  return -1;' M* O0 y' E( g  O, r
}
/ H6 ^5 I9 O& q7 b6 _/ Rvoid String:refix()
: \7 G* l2 I8 C4 \( q0 E{
+ f, J/ x. H) I; T! J! T int m=Length();
- n- Q; ^8 B& t6 x  I delete [] pre;2 {( U3 P3 b0 i7 H! A
pre=new int [m+1];
8 d" H( v( S/ ?3 U+ P! G* c pre[1]=0;
; @1 m$ E: |- G& Z; E int k=0;
  }3 I6 N( B3 r, _ for(int i=2;i<=m;i++)
8 d* e5 x- x; A. p; Y {- Q1 ~0 X  B2 h( p- \* Y6 ^
  while((*(str+i-1)!=*(str+k))&&(k>0))- C. L; O* l" X+ E
k=pre[k];- X$ \7 j( z1 _8 [2 Z. X
      if(*(str+i-1)==*(str+k))- \0 R: Q; o% e
pre=++k;$ M0 o7 y% I8 U( _# M. \
else
. y+ |4 l0 |$ n5 W pre=0;
* X0 W) m' Z. n7 N. l }/ u" O2 `$ U( @$ N. X
}
6 h+ B  ]* Y$ j' O0 @) L2 `void String::ModifiedPrefix()  |% Y* {" U" }( i. \
{
' ?6 U4 _( i4 U) f# | int *f;( Y! g1 U3 b, R4 d& T- i
int m=Length();
) P$ h' E- t; J f=new int[m+1];
7 ^( i, Y" V/ A% x Prefix();
: d/ g4 p3 Y  O6 {6 V/ f) @ for(int i=1;i<=m;i++)
) b  t+ D' m6 ^4 ~ {
. y7 U, D! f! I5 K f=pre;
6 a7 Y1 S$ Y( h+ q' T* W }
* F& Y3 U2 b! ] for(i=1;i<m;i++)
3 p2 E$ M8 }& H* ~$ G6 P7 o" s% n {
  p) {8 Y, C' F  int k=f;/ u, U' g1 s5 f8 t
  if((k==0)||(*(str+i)!=*(str+k)))
9 l  N. c! o6 |3 R& x' R pre=k;
$ M, u! U# P7 D  L8 W2 e  else
% f% O; P/ P: a% f9 e, k2 e pre=pre[k];/ c. k" O9 W* [& Q1 ~8 ?4 U
}
$ j4 H4 q% K2 u# n4 w# O delete []f;% [+ c2 ~. }& m. @
}
8 @0 Q0 m/ \( \+ Y  }int String::Match(int i,String& t)+ i* c% K1 c+ x, a& l. B' Z' @
{& z3 t% h3 y0 l, Y
int j=0;. M8 w/ N: Z- O3 k
int n=Length(),m=t.Length();! E' D1 y9 u6 k1 u) u: l8 w3 ^% @0 E
t.ModifiedPrefix();, w1 ~) [- K. o7 y. I  d
while((i<=n)&&(j<m))% g: c, }. F; f# E
  if(str[i-1]==t.str[j])1 K7 T0 A& h8 y4 B* K" b9 f" Y
  {
# u6 }. K+ ~/ }3 V# G! j i++;" I: b" X* L4 p# T) X" h
j++;; P1 u9 m& M' J: g& H# f0 R
  }
% q2 L5 M. A2 @! c/ R( P  else ! a! j* e- }& n! F% A. f. J
if(j==0)
' n& C& R0 h  f       i++;
: e+ C+ t( j, I" e( |    else " b3 O4 S- F5 g3 v
j=t.pre[j];  f$ E' M/ @& L7 R* L
  if(j<m)
, b0 F0 l/ r0 f9 d) f# l: u return 0;" H* R) W2 P5 X8 M7 S2 k# ]0 q
  else . ]+ `4 w3 Q3 g/ ~
return i-1;
; s- z! S0 M; H" c. W+ m}
  e  U4 ], S7 c3 _) E( Sint main()
' a' g+ r. A9 B/ q# r{' ~7 M; H5 ^7 N
if(in.fail())
6 o% u# W& @7 {- c& a, m3 }0 | {! a: S0 ^3 o5 G+ Y! T: g
  cout<<"the input.txt is not exist!";- {  \; A" M+ @6 w
  exit(1);}
& k* A1 J0 h5 }% |0 Y int i=1;
* e/ E0 E6 V5 k6 t7 ~2 D, _, G String s,t;
! o: G' }0 J& Z( U. r/ i s.ReadString();$ ^* r9 L$ V8 Q3 D0 z
while(t.Rs()+1)( ?; ~7 m) C) W, K3 z. J
{
9 V) [4 H# B$ f3 E4 s  i=s.Match(i,t);/ r' T0 Y# ~' c$ C! Z0 F/ q. ]3 ~
  if(!i)' E6 r5 K; n/ d" p, ]
  {! Y* [$ Y+ a2 o/ n5 }
   out<<"No"<<endl;6 @# I# {2 ^, S9 h
break;
6 K/ y+ c3 R& k1 J% o! C  }$ K/ ?% ~. p! |
}; i0 W, e. B4 M4 c3 G9 K! b
if(i)3 s& ?# o+ W1 k) P, g* C
  out<<"Yes"<<endl;
5 b" a. z9 X) s; `. v return 0;" w9 O+ j8 N; A$ d4 O( z
}