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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
- V" O& D( _3 uusing namespace std;
ifstream in("input.txt");
3 T$ i5 k' U- z9 F! f/ zofstream out("output.txt");
class String
{
# J6 k4 d& A6 d6 y5 C5 I8 o  public:
) ]" c* x6 v! ?5 n" Y; _ String(char *s="");
String(const String&amp; s);
  s4 z/ _! ~+ Q0 e1 f$ T, Q/ F  J ~String();
6 {, |$ T( E7 v& L int Length() const;
int ReadString();
% Q* K" [; k9 ?! ~  J  m8 T* J% m int Rs();
5 L9 k- d% o1 F; f void Prefix();
void ModifiedPrefix();
, Q% w5 g. {& x int Match(int i,String&amp; t);
, ~2 |, w" {4 `* s0 B  private:
5 }, s  B* V' w$ q% l   char *str;
2 B7 n9 {$ J) D2 s$ t4 _8 c   int *pre;
8 {& z# Q- J7 z   int size;
1 C+ C, u$ ]) b5 G% }. B: Y};
String::String(char *s)
# @" F( U# ~- t, X# H{
/ A! c- e' s3 | size=strlen(s)+1;
' O3 _0 g8 w: v$ N/ n' q, H str=new char[size];
+ H# J4 {# u6 D9 N; W/ X; I, W7 \' f if(str==0)
  throw "error";
strcpy(str,s);
/ [3 L; c, @* e; e$ j pre=new int[size];
if(pre==0)
3 }. C/ `; p) c1 Y" J; Y  throw "error";
}
String::String(const String&amp; s)
{
8 k& n+ P! j% x! L) m' f size=s.size;
( g0 D! y& X+ m, ]4 `$ J str=new char [size];
if(str==0)
  throw "error";
strcpy(str,s.str);
' H) i: m8 W' J0 x9 C+ u3 n pre=new int [size];
if(pre==0)
  throw "error";
( A& [( h% T6 ?4 G3 Z}
2 U$ y# m6 p& z$ G* W+ g) ^$ M- kString::~String()
{
delete [] str;
5 l; j; M! r" F2 f, l* A2 y2 E delete [] pre;
}
3 T4 \" b: `) A  Yint String:ength() const
{
2 q7 h; o! P% s: B8 f8 T; @0 J return size-1;
* @# \0 y* v# L, \# W2 n}
int String::ReadString()
{
char tmp[256];
    if(in&gt;&gt;tmp)
% a0 ~3 ]9 B$ { {
  delete [] str;
  size=strlen(tmp)+1;
  str=new char [size];
$ f9 i' j$ y0 \9 |  strcpy(str,tmp);
# N/ u# f( C6 \/ I6 D; f  return size-1;
7 t3 t# H  S1 t9 z+ P# b }
  J0 I0 Y6 E# ?6 t% y3 g' ? else
  return -1;
$ `; y6 l+ j3 O& [$ X, L' q}
! o! a: z# f6 \- g+ i  Q5 Zint String::Rs()
9 c) Z: h: J9 Y3 S' ?0 n( f6 O/ {{
char tmp[256],c;
0 j' X  ], k5 C1 J$ i, j# s int i=0;
# h$ o# l! E4 v while(in&gt;&gt;c)
{
  if(c!='*')
  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
   break;
, Q# {+ M& [5 Z: G }
if(i&gt;0)
{
  delete [] str;
  size=i+1;
  str=new char[size];
  if(str==0)
   throw "error";
  for(i=0;i&lt;size-1;i++)
+ y! A4 ?7 O( ~) n4 k      str=tmp;  
$ Q( Y, Y" p/ f1 [: y" I9 z* d  return size-1;
/ Y) T) U  h3 ?/ y! r }
else
4 w: C$ R* B2 X$ f1 D2 |  return -1;
}
void String:refix()
{
int m=Length();
5 W3 q7 K8 v1 n delete [] pre;
4 F. k9 }0 ~8 Z: v- z pre=new int [m+1];
pre[1]=0;
int k=0;
4 X1 }% n2 O! R# d6 p4 B for(int i=2;i&lt;=m;i++)
{
; D. m; E1 M9 }. l6 c; A+ H  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
3 y+ B. A" s0 A7 G3 b$ g   k=pre[k];
, i2 z% ^9 K( ]/ |! _6 Z6 q         if(*(str+i-1)==*(str+k))
+ H+ t4 H) W: S$ H+ n    pre=++k;
   else
$ K! F2 r0 [% B9 v    pre=0;
& ]; d& w. ^- U* F; l, x }
8 E6 n3 t; C: w}
void String::ModifiedPrefix()
) H) Q3 {# k. A2 K- B. w{
# ~) n. C4 p- B# i int *f;
/ Q/ a  y( w8 {* L  A: P int m=Length();
f=new int[m+1];
6 {; D# ]' z9 o, ?9 V+ `+ \# W Prefix();
for(int i=1;i&lt;=m;i++)
7 a) O, Z" w3 p% k/ `& c {
: |# l: g$ Q! e, K0 @    f=pre;
}
for(i=1;i&lt;m;i++)
{
  int k=f;
  if((k==0)||(*(str+i)!=*(str+k)))
4 u; e6 H: j, O" J; K   pre=k;
1 y% l; ]: {2 e" E3 ~  else
$ I9 S( M: m  C) L. Q1 k# n5 M   pre=pre[k];
  {% C0 @/ V* v  k  i9 p1 K3 R# | }
delete []f;
( f& g' {. i0 D( q% n" t! p}
int String::Match(int i,String&amp; t)
4 R. F+ K' m" m7 |$ f7 L. N. m* z{
int j=0;
int n=Length(),m=t.Length();
t.ModifiedPrefix();
while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
* f  f% V& }1 Q8 c' l  {
4 ]' M* g& n0 n- y  o   i++;
  X& d) l/ [1 k& A6 g   j++;
; O3 @/ @/ Q) g, b  }
. {) o! b* y; u: o  else
   if(j==0)
        i++;
( @- v6 S6 G$ N* C      else
2 V( J: N, d$ X1 l( V1 o    j=t.pre[j];
  if(j&lt;m)
6 t6 ]# t* }, `6 d   return 0;
  else
5 t  R; b2 X& |2 f  F- F# G   return i-1;
}
5 u5 M# `# i7 l' u$ h( z# dint main()
{
if(in.fail())
* k) |: R/ ]: p2 [6 Q {
# G; {+ w& q7 Y; O  cout&lt;&lt;"the input.txt is not exist!";
+ \: U6 I$ P2 x% j* h" F9 G9 S6 M  exit(1);}
int i=1;
String s,t;
s.ReadString();
0 I# N+ T1 ^4 K while(t.Rs()+1)
{
7 c. U7 W$ Q+ T7 i- F  i=s.Match(i,t);
8 D  O) p! G3 A: W2 h6 l$ m- h  if(!i)
  {
2 l- {4 e& N& }4 B$ o6 J9 f      out&lt;&lt;"No"&lt;&lt;endl;
   break;
  }
. [/ D; ]% x. y9 H; T# m7 e }
. L0 F- m1 ^+ U. Y& S7 B5 K/ b- K; m if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
9 f: X9 r+ s3 a! F- e return 0;
! f, Q' g% z$ n% h" V}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看