查看: 4228|回复: 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;
4 f9 u% E) {1 W: d3 E  return size-1;
) Z* l8 u* O5 f. `& f% X5 @ }+ \/ ^% n* C" I7 [9 D
else# D! ^3 h; y( w9 t6 ~
  return -1;
7 ]& N" o8 v4 c2 c3 d& i# X}
8 g7 L$ \3 u2 ~! Y4 ^# a: E! Fvoid String:refix()
1 N$ \0 c; _" M4 K: T, p% O! D{/ g0 x; |6 ]5 D/ D: @
int m=Length();5 S1 u/ F, ~7 ?: j" z5 U$ f
delete [] pre;
' }+ w3 Y3 L1 j  `" a pre=new int [m+1];. {1 q+ b6 t. ~7 p6 Z- v% L
pre[1]=0;  [) t3 I. b3 D4 t
int k=0;8 y% c4 h3 A* R8 `' ^2 n* ?
for(int i=2;i<=m;i++)
* j) W  u7 r* N {: N/ y. H) k4 S2 E! i( T% T
  while((*(str+i-1)!=*(str+k))&&(k>0))/ E$ r* e4 a( @+ x1 {# x
k=pre[k];
/ R- D% j# i5 O  n. _7 K# g       if(*(str+i-1)==*(str+k))3 L& D3 ]+ B% L
pre=++k;5 {3 @8 q  [% D9 p. j
else% ]( E0 ?2 P2 Y- X
pre=0;" F7 y: M4 Z- K  n) i
}) w2 Q* _: y! C% ?3 ^+ Q! x0 z
}5 d' B  ~9 j) m( i. c
void String::ModifiedPrefix()
& ~' }0 Z" F4 D' d& S* d{
' {5 u* Q( Z% a* o int *f;
  o" a2 V0 n9 i: j' k int m=Length();
( G, c3 A! s4 b f=new int[m+1];9 b4 ~0 @, f! z( l
Prefix();2 p7 }) s* I8 G& w2 m- G. S
for(int i=1;i<=m;i++)
! F% x: A+ p% G( j  N: A4 [ {
* @! e, w/ E9 X$ W+ g) Y$ j# o9 M f=pre;
6 H) H) U1 t' |( X" C }1 w7 |$ ]: M' Y$ L" a% W4 p
for(i=1;i<m;i++)
( t( p1 ]. |/ M {9 u4 B+ \( b1 Q) d- H9 C3 R: z
  int k=f;& {0 m; ]) ?: E# c. s
  if((k==0)||(*(str+i)!=*(str+k)))
# X+ M) W- y! K; O pre=k;$ C$ D# W: d8 A! r6 }
  else
! R. s% s9 m# k" z pre=pre[k];
2 Y- D. \' a" n5 r }
$ E! x1 q/ i  s- b delete []f;
% Y4 k$ U6 G3 F6 v7 e+ o}
2 x& b: z( p6 a6 cint String::Match(int i,String& t)
) o( ?$ W, {% e4 k; R4 H: Y{
- N: y5 V+ x* X+ [# u6 V! x0 K int j=0;
  {. F0 Y6 [8 x3 h3 a; u1 q int n=Length(),m=t.Length();& U9 J) U$ E. S6 y5 |7 j
t.ModifiedPrefix();
$ @( l/ l" `# \6 L. S while((i<=n)&&(j<m)), M# ~( }% v8 v1 A/ {) a  d; Z! u
  if(str[i-1]==t.str[j])3 y2 W: I: _+ i+ B2 K' v3 {
  {5 z) _1 ?  I* d8 @9 J$ ~$ E
i++;
/ e" r" Z" M# s" f( e( H j++;
" @" M+ S' F& M9 {% B) s, t  }
$ u, g: n9 t/ p# T, ^* v% H  else
1 o" G" d# W4 ^$ l if(j==0)6 n0 P! L& ~- ]  [2 B( G' @* x6 Y
      i++;9 C8 s! q- `; G' m8 }' I
   else ! ^6 H% {7 a9 h+ g
j=t.pre[j];
/ @# R3 L, t* e' N( }: Z* t  if(j<m)
. t& {- l- c; O1 h return 0;$ D2 N' n* j- _$ Z+ v4 t
  else
7 y) g+ G* r1 A% s- e( d: Z5 ^" D return i-1;" R3 D, j8 S# Y7 e# y+ ^
}1 R3 V1 T9 R8 ^% `1 j: [% j5 v
int main()8 G/ L5 b1 H; [8 r/ o1 R- Z
{! f- g( p$ ^6 V2 a; a) A0 b; z; B7 K& n
if(in.fail())8 K& I3 l, D3 C/ t7 N
{
: o( e4 j# ~# |  d8 a$ w7 u# w  cout<<"the input.txt is not exist!";
& a+ K. k& w- \  exit(1);}: Y9 D+ p6 L- C* c3 G9 w
int i=1;: C, e: H: j$ \# Z
String s,t;9 C1 F: B4 g6 t( I( L7 v3 }
s.ReadString();8 i* b$ v0 D4 ^3 R9 i% I
while(t.Rs()+1)
0 A3 q- P* A- S7 k) A {: A+ G/ ]- A0 x2 h1 `/ _
  i=s.Match(i,t);
+ W) N  ]$ \. h* ~1 ?  if(!i)) C: j! k; N3 b( ]+ q0 `( \: m
  {
8 l. z; P' G. k( p  O    out<<"No"<<endl;
- c- R! N5 c' {2 N: w, o break;7 d, k) D# ^# a0 [3 g
  }7 {5 s( ^" q) T' s% b
}
" k' o6 T. B2 N, I: A- L2 d if(i)
5 G; ]$ Q* f' y2 g" q2 S8 J9 h9 D' [" Q  out<<"Yes"<<endl;$ {  [7 _8 I: l; C8 c. A; b
return 0;
. j5 P) H6 z3 d/ v0 y& A}