查看: 4261|回复: 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 c8 o" p6 M) L
  return size-1;
$ ~2 q( H( `7 U }0 O, {: q- I0 u" i# T% `
else1 N2 f9 X3 V0 ?2 U, b4 h
  return -1;
" C( n5 ?) Z- j) ?}
5 U2 `8 a) @& Y- _5 a9 q: w3 l2 ~void String:refix()0 O, j" ~8 v- ~+ b2 s/ W1 l" r
{
0 |7 {; M# l$ g/ a+ z7 P; ~1 Q) v int m=Length();+ ?+ ^& x$ e- J: G
delete [] pre;
0 [2 y4 `) s+ g3 c pre=new int [m+1];
% T* S6 i& y" W; K7 G. w6 N pre[1]=0;
; [# h+ Q' O4 [0 X int k=0;$ p5 l/ q, _" M: T& _$ `  U3 u! g- S
for(int i=2;i<=m;i++)5 X( C2 f: D( s. A
{
3 V8 o7 T: {, T  while((*(str+i-1)!=*(str+k))&&(k>0))* i- i1 P& t& H1 }5 T& A7 R2 `7 B3 G
k=pre[k];1 C3 v! X3 Y3 G
      if(*(str+i-1)==*(str+k))
/ H$ A' t$ R: A  j' i pre=++k;. x' c3 n4 j  R
else8 O* ^# V. k: d- H. E0 g7 E
pre=0;
) v5 \* R# G( ?1 i3 z  m }
7 [  @  E- x3 |6 c3 U8 Q, n0 R! @}
' x1 [, ~" o% l6 s0 F0 P7 b' Ivoid String::ModifiedPrefix()3 l, u4 s! B1 V- L! i2 m1 ^
{
" q6 o; e- C* S3 R+ H$ R; L int *f;4 P! H, L0 M9 W0 ^
int m=Length();8 Y* n2 P- D3 v8 v4 D. s
f=new int[m+1];( e6 w" E& Z# I. `$ o
Prefix();
+ d* r# x2 t/ Q for(int i=1;i<=m;i++)" _. j- Y2 g2 K& ]! V
{" \$ B/ W+ d$ b2 n/ v; l) c: d
f=pre;
, o- s, [- ~$ A' Z) o }4 @, A6 G& N3 q' r$ a9 |9 y$ H
for(i=1;i<m;i++)
+ ^/ U$ p0 V6 o% a: [2 ]8 ^  A {
4 J5 p6 r# |+ D2 M: g  int k=f;& d  ?. [; @* P& a; F
  if((k==0)||(*(str+i)!=*(str+k)))! r4 w; V* C* k
pre=k;$ I" ^6 _( \4 |* G; G
  else
' y- O6 J' g! R4 C* } pre=pre[k];
! C8 m( w$ {0 p' T* O* c }
. e5 F  V, Q8 Y delete []f;
! p  H  o' }) ]! m5 K}7 N% t* |/ A1 C& ~
int String::Match(int i,String& t)7 ~( W1 g7 `6 d. ^9 c
{
. }( m) c* Y6 `, m6 w int j=0;0 S# T0 h/ G2 H9 R" I' Y
int n=Length(),m=t.Length();
" s: L+ g' n& `+ _; H1 f t.ModifiedPrefix();5 j" G) e; S0 N# Y( L9 J& J
while((i<=n)&&(j<m))
: M5 Y2 r8 r7 m$ U. z  if(str[i-1]==t.str[j])& |/ S' v. Z& s' t0 P
  {5 T; N* K1 h7 N! M) J6 d& {1 h
i++;: G& G; m* U3 b: F& a
j++;  e% W1 C( L2 A
  }
9 g1 O9 h$ U* o9 f3 f; t7 }- r6 Q9 @  else
1 Z# W2 @, b& Z% l* K. v" k6 W if(j==0)
# Q# p7 f7 s% E/ ]       i++;
) V, I: F: l+ L4 _! u* {    else % D1 N3 q( p2 B) s$ r8 h
j=t.pre[j];
& C1 k! o9 `# S* l  if(j<m); V! w# j) ~! V# K
return 0;/ x; d7 X& T& o  b5 ^' L8 D4 \5 T
  else
8 d8 L/ d/ ?' p- U return i-1;7 g6 o# v7 |' y# \+ m+ z
}/ S2 r# a( ]& l" K8 u, D
int main()
4 o# Q3 Y/ Y6 r( N$ e* `{
6 F4 M2 Q. o8 o) n! {1 W if(in.fail())
* J- s- C6 l4 J  s$ B {
2 j5 u& j% Y' _% E& j  cout<<"the input.txt is not exist!";
, H9 j3 L4 J3 D% T$ C( y9 o8 B  exit(1);}
7 f1 H. e  `) L3 d, X6 y& l# N0 z int i=1;
" l/ [* U0 l+ _+ m0 j7 l: P4 c; `: f String s,t;
6 U( [! ?! L; y3 J5 D/ F s.ReadString();' Q8 Y2 A# W' z/ v$ w, ]
while(t.Rs()+1)* S# l  r( e9 V' d9 t
{6 u3 [' c$ g$ d
  i=s.Match(i,t);# h. f' h7 c& p
  if(!i)
/ `8 W7 C7 a" ]% e$ t( D8 D  P2 D  {) N2 t4 x2 |' r# @! j
   out<<"No"<<endl;
. i0 }& [2 v" ^8 h+ p  ^% |4 F break;
+ W( r" S5 o; A7 j- f: y. O  }$ Y+ p7 Z2 d& ^
}
. k4 q# I4 u! }1 M. |& i( ^6 z if(i)
  out<<"Yes"<<endl;5 {1 P% z' [# }9 g0 ~% O2 j# U* o
return 0;% s, L3 Q3 H6 v4 G+ ^) A6 a
}