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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
using namespace std;
ifstream in("input.txt");
" ?  }* Z6 T: ~, Cofstream out("output.txt");
5 Q& n& i# g' m; l; O- Mclass String
{
  public:
String(char *s="");
; `3 U8 ]9 i$ k* o  O# S7 ^2 z, I String(const String&amp; s);
~String();
int Length() const;
int ReadString();
int Rs();
3 V; ^7 ~: A1 y, o void Prefix();
void ModifiedPrefix();
6 }$ W. R% C8 k" K int Match(int i,String&amp; t);
4 v9 ^  @3 |0 z7 G  private:
   char *str;
" v0 S( ^- `7 @7 M0 I0 a   int *pre;
   int size;
};
String::String(char *s)
. a7 Y* V& Y! s: K{
6 N6 d, r0 O! ~: F0 I size=strlen(s)+1;
0 S# c1 e* e8 G% R" o1 l& S- l str=new char[size];
. _' W9 L9 H* z6 b9 g if(str==0)
  throw "error";
strcpy(str,s);
# P; c+ B. L$ G- C/ ~, T pre=new int[size];
if(pre==0)
  throw "error";
, {  ^. \/ O& p  M+ B}
! |5 V& E6 E1 y. f- FString::String(const String&amp; s)
{
size=s.size;
1 ^8 Q8 P/ I' g" F  u$ N* C str=new char [size];
if(str==0)
9 n3 x7 i- P) w  f2 H  throw "error";
strcpy(str,s.str);
pre=new int [size];
( B4 l, f( S+ C: @# H if(pre==0)
  throw "error";
}
String::~String()
: P. o4 H5 K  B4 s# C6 ~{
delete [] str;
delete [] pre;
* z6 p* Z) a; a: E5 r5 J4 T}
int String:ength() const
$ C$ u0 z% b; p5 p{
return size-1;
! V' r: P& D( `& F  V1 Y}
' g7 E: {9 p5 s9 I- S$ `$ H6 x2 iint String::ReadString()
{
char tmp[256];
    if(in&gt;&gt;tmp)
4 Z/ V& N4 ]. j4 l& i {
  delete [] str;
  size=strlen(tmp)+1;
  str=new char [size];
  strcpy(str,tmp);
1 _( z: W0 v+ [- W3 A% x1 `. b  return size-1;
+ {, V, H1 y" ~( y8 L, Z }
3 ?# N* I) F" V, M else
  return -1;
  t  l8 Q- \' K  v7 g% c/ D! q}
; H2 c! ?, }5 `" }! Lint String::Rs()
# ~7 K# F' K8 Q! c{
char tmp[256],c;
int i=0;
9 x$ r( B# ~4 u# w, m  x4 t/ K while(in&gt;&gt;c)
; e+ _* M; G  [& O3 w {
; |4 D* F: V# {9 _; t  if(c!='*')
  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
   break;
}
# p4 e- j% w: C2 p9 v if(i&gt;0)
{
) @2 f7 K4 `$ u& t% `  delete [] str;
  size=i+1;
  str=new char[size];
  if(str==0)
3 J7 [3 \" ]' Z6 T, @2 h' r# C! ~   throw "error";
  for(i=0;i&lt;size-1;i++)
' |3 Q+ U9 s& f. |* ~# Z' L      str=tmp;  
  return size-1;
1 y# d3 I, P7 p8 d$ {* a }
else
  return -1;
}
8 H# ~  u: _; L- D/ V6 T" Cvoid String:refix()
{
int m=Length();
' [$ `, z8 T& h% _ delete [] pre;
( r' ]- {3 h; x8 t& ] pre=new int [m+1];
) m- e+ R" d6 b; @% m$ e, ~9 K pre[1]=0;
; _/ ~. G' b& R8 | int k=0;
& H3 K9 X) V: R: ]: q% U for(int i=2;i&lt;=m;i++)
{
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
% s0 h/ P8 V; j6 b  B" P   k=pre[k];
         if(*(str+i-1)==*(str+k))
8 E# n* h7 C! P* y) u" J    pre=++k;
+ V8 o1 R0 q' D" U; l3 G1 \1 {% G   else
7 d, `7 D0 z$ t; @    pre=0;
}
}
) z) w+ i/ i4 Xvoid String::ModifiedPrefix()
" G, m' D0 g: @% N1 u3 _7 n+ w3 r' I{
% X; _' ?( k6 f' l9 o5 |( p/ f3 A int *f;
; `  J* k( c# e3 W; M% C int m=Length();
f=new int[m+1];
Prefix();
8 j4 @' r8 k# x1 Q* s7 M% f+ @ for(int i=1;i&lt;=m;i++)
{
. S4 i1 }8 P6 v2 T- r8 k    f=pre;
0 N6 I9 H" ?+ \( f6 p: ?, \ }
4 [1 r/ ^0 F) D2 U for(i=1;i&lt;m;i++)
; M( b: P/ g0 n2 P! c- m& Z {
8 l" \5 {% w; ?/ F0 q  int k=f;
9 o$ W3 J2 W5 v* S; @$ L2 @  if((k==0)||(*(str+i)!=*(str+k)))
   pre=k;
+ v9 m8 n( m! I4 x3 b/ j9 T2 A# r  else
   pre=pre[k];
# `7 `2 }; R6 [' {* q2 T# H }
$ T# ]8 o5 G* A  z2 |* \ delete []f;
}
int String::Match(int i,String&amp; t)
0 K' j+ J! i, c! \6 n6 `+ j{
: g, p7 Y$ f# w0 N& F: A int j=0;
4 }1 n) E& a' { int n=Length(),m=t.Length();
t.ModifiedPrefix();
( I7 b1 x! a8 c/ u while((i&lt;=n)&amp;&amp;(j&lt;m))
3 L- z. g6 c' O/ ~! A; E- `* O  if(str[i-1]==t.str[j])
' p9 B! s7 p2 p' X0 g. P3 w0 f  w6 B  {
! k+ l+ o6 }  G9 s+ D2 u- Q   i++;
   j++;
) K# v: y- d9 g% O" S$ C3 _  }
  else
   if(j==0)
        i++;
      else
    j=t.pre[j];
  t( O! x* c+ o" u! M  if(j&lt;m)
   return 0;
  else
   return i-1;
}
1 H, |2 f9 u1 w6 c4 ?int main()
{
if(in.fail())
{
  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
int i=1;
String s,t;
5 V  x  a$ g8 c4 a; V. p, y s.ReadString();
5 F0 p) J7 [+ X0 r6 B! G( p while(t.Rs()+1)
{
" A9 ^' s# n# S) f' |% Z  i=s.Match(i,t);
  if(!i)
  J$ e4 m$ c4 }5 C, h- X& z  {
      out&lt;&lt;"No"&lt;&lt;endl;
   break;
  }
) Z, @/ `: x$ F" T9 u. O }
( b" Y  s+ R# ]0 T4 U4 @ if(i)
& R, K3 {5 L7 o1 t+ N6 p0 m% M+ ?  out&lt;&lt;"Yes"&lt;&lt;endl;
$ [% H9 ~. C7 D& i" q- \- j return 0;
}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看