间隙字符串匹配问题（c++)

lynnyan

<>很经典的一道问题，我想大家应该都会，我这次只是想帮助那些还不是很懂得人，还是一样附上解题报告和源代码。觉得好的就顶，主要是用模式串来解决。</P>
$ c# r' s. N$ n( H0 r' m<>[

游客，如果您要查看本帖隐藏内容请回复

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
. C/ g7 ~' E4 A$ I+ busing namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
class String
{
  public:
: }  [3 r3 m4 H5 S String(char *s="");
5 C; x/ k  P2 |1 n  W8 r, H0 e String(const String&amp; s);
~String();
int Length() const;
* x. c- C  h) R% `- Q int ReadString();
int Rs();
void Prefix();
void ModifiedPrefix();
( C( y8 g0 ?* Y7 I! q8 p6 K# y int Match(int i,String&amp; t);
  private:
. V: l, U! \, y' Y  C" j   char *str;
! j& a( _- l+ q   int *pre;
   int size;
};
String::String(char *s)
{
size=strlen(s)+1;
str=new char[size];
if(str==0)
  throw "error";
, s  C# J3 d& T( G3 T/ h" [ strcpy(str,s);
pre=new int[size];
if(pre==0)
  throw "error";
}
9 w, {( D2 o" R5 @String::String(const String&amp; s)
5 V# z+ v' l% ~3 G' k5 @{
size=s.size;
str=new char [size];
: C, k  `7 [: f# K8 H9 }" ?6 v" |& W if(str==0)
  throw "error";
strcpy(str,s.str);
5 F4 ]& Y& }. ^8 f6 }7 p pre=new int [size];
% e' Y9 V  r9 I5 c if(pre==0)
; A1 s8 Q9 T) L( @# P  throw "error";
$ c, ?' f( t0 v5 A5 ~7 v. W. {: S}
) V& Z# |7 h1 h* g- n: SString::~String()
{
delete [] str;
delete [] pre;
( n+ b( ?3 f8 k$ f}
0 Q1 U; {0 z! H9 r0 W' iint String:ength() const
{
) t' s- C8 Q' E- `% f/ h return size-1;
- K  K+ \3 w) P8 |. Y}
int String::ReadString()
{
char tmp[256];
7 {1 n  k; t, }4 v3 J8 P    if(in&gt;&gt;tmp)
% ?" O9 s  u5 n; W7 L {
% C! J* v7 \8 E! s3 m  delete [] str;
  size=strlen(tmp)+1;
1 J# T) R) S( l& R4 n  str=new char [size];
& g2 ]" O$ N, _" o' i  strcpy(str,tmp);
  return size-1;
/ ^3 m* d- ^- R) a* g }
else
  return -1;
}
int String::Rs()
{
7 P- U+ r- h( U4 s# c( _3 U char tmp[256],c;
7 L; ^3 j2 B$ }# P  [9 R7 [ int i=0;
while(in&gt;&gt;c)
+ A% O/ g4 z( }: v8 _+ `( ?4 o {
8 A7 i% [: u+ [+ K" w  if(c!='*')
  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
   break;
}
5 P; l7 y8 f3 C- w7 U if(i&gt;0)
{
4 r7 ]* H  W* H: T  delete [] str;
  size=i+1;
  str=new char[size];
$ @4 ]) f4 L2 Q2 _" \  u  if(str==0)
   throw "error";
5 g4 _/ }3 Y+ a  for(i=0;i&lt;size-1;i++)
9 F* J0 X9 `) V      str=tmp;  
, W& l5 V' T: w4 G  return size-1;
}
7 s( }* {6 |5 {, o9 L6 A7 N& ] else
  return -1;
0 G+ E; L/ I9 r' r' k' X}
" O6 A+ Z& c$ M8 cvoid String:refix()
{
int m=Length();
delete [] pre;
pre=new int [m+1];
pre[1]=0;
# m+ X' d4 F; Y7 M8 t int k=0;
for(int i=2;i&lt;=m;i++)
- i1 U; U; T! W {
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
   k=pre[k];
         if(*(str+i-1)==*(str+k))
9 Z: H6 s- X7 h    pre=++k;
   else
    pre=0;
}
}
void String::ModifiedPrefix()
3 ~8 s3 }4 _5 U" B$ _{
8 [8 C% B0 f: W) z# ~4 x int *f;
/ [! _4 Y9 z- D int m=Length();
+ D3 p3 U3 H3 f f=new int[m+1];
Prefix();
for(int i=1;i&lt;=m;i++)
{
7 w  ^6 d1 S0 Q# B$ w1 T/ L' m    f=pre;
}
4 i9 ]; b  {9 S) L+ [; H4 @ for(i=1;i&lt;m;i++)
{
  int k=f;
" R. h2 t4 L  r& c2 \" j; e9 ^7 R$ ]  if((k==0)||(*(str+i)!=*(str+k)))
+ K9 w$ q3 t3 d. |3 t   pre=k;
6 o3 X4 x# ]$ @8 Q2 o  else
   pre=pre[k];
}
  r: z# j* z# C8 W: v delete []f;
5 F' B$ p, W$ b. E) T1 R8 y" c" Q}
int String::Match(int i,String&amp; t)
{
int j=0;
int n=Length(),m=t.Length();
$ Q1 g. _5 U( V. |7 q8 k t.ModifiedPrefix();
% Q" @4 q# I) B! O4 c while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
9 X) w0 h' H! ?* b  {
   i++;
; p! K8 Z$ p6 W+ c: O   j++;
  }
+ E6 J' d! S0 X. ]: ]/ X  else
   if(j==0)
* q% P: N  \" Y+ M! V        i++;
      else
& x9 }0 [" ~  e    j=t.pre[j];
9 @9 Q7 D6 r" I$ t& o" T* R  if(j&lt;m)
8 o6 v# M9 [- z1 Z+ Q   return 0;
  else
   return i-1;
}
int main()
{
if(in.fail())
5 g2 A9 d- F3 [% q* d% ^0 X: N' j* b {
  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
int i=1;
String s,t;
s.ReadString();
while(t.Rs()+1)
! a; V. b8 E1 |, V$ \2 q* ^ {
  i=s.Match(i,t);
8 n. v  p6 f. l, z: V/ j/ }, m$ a8 F  if(!i)
  {
0 V3 n6 L0 S" ]- A/ T3 ]$ }      out&lt;&lt;"No"&lt;&lt;endl;
1 x! m& p3 g4 c* p! V7 x1 N! L9 {   break;
  }
: L! {4 u7 q* e$ E }
if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
return 0;
1 e. g* n( c. u( N* {6 m+ I) }0 F}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看