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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
! P/ b$ N3 m9 R% W, G" q$ b; m#include &lt;fstream&gt;
9 J5 D, z7 `3 A2 Q$ W" N) `using namespace std;
* Z0 S7 Z1 x8 hifstream in("input.txt");
ofstream out("output.txt");
  d, [. C0 @7 O! Z* [class String
{
! J6 k4 w3 R+ _" A  public:
String(char *s="");
# m/ y; `, v" P7 e String(const String&amp; s);
/ P; [; l; V, n& H8 B& R' k1 m; n ~String();
int Length() const;
1 p: P% a" H2 I2 N$ s int ReadString();
int Rs();
void Prefix();
void ModifiedPrefix();
  T7 O9 h" K7 r& T int Match(int i,String&amp; t);
: D+ i  A4 F. W' A1 P1 P7 y% i  private:
   char *str;
   int *pre;
   int size;
# G" W$ Z( L2 p; N4 V8 U1 r) w};
' o- V7 v* Z$ H4 l2 tString::String(char *s)
) n5 E3 d6 t4 ]{
size=strlen(s)+1;
str=new char[size];
if(str==0)
8 [) `. N; O3 j% z  throw "error";
+ T" R; d7 N5 ~# o4 K8 e2 D% R strcpy(str,s);
pre=new int[size];
/ v' M, {$ b: W if(pre==0)
  throw "error";
$ n( g, G; y0 H, A% K9 r7 G8 }: z}
% z# c" A% D* F' VString::String(const String&amp; s)
- O9 i6 j9 L- L+ u7 W% s$ l{
size=s.size;
str=new char [size];
if(str==0)
  throw "error";
  L2 D2 ?- J4 j# r! O' ?0 z strcpy(str,s.str);
pre=new int [size];
if(pre==0)
  throw "error";
' u) a$ z5 S+ {) A! ?2 v  v}
9 ?; c( C" l* t% }String::~String()
0 h6 y& \+ t5 j. ?1 e7 @/ Q# S{
delete [] str;
" `% X' F2 P9 l5 Z8 ~ delete [] pre;
}
/ a9 O7 T$ p$ oint String:ength() const
! s5 `7 Y. ^+ r{
6 y# w2 I5 n# a0 c( D% f, @ return size-1;
0 b$ q' z5 J' f( O$ I  u% \}
# y5 j: @+ Q+ I# _/ I6 H( Sint String::ReadString()
4 M/ g* [2 G5 h0 K3 R- \0 i{
char tmp[256];
( ^! y0 w- S6 U' \8 l. j- _! ~5 \    if(in&gt;&gt;tmp)
{
# M/ ~/ B1 ~0 _$ G" d% W% L  delete [] str;
  size=strlen(tmp)+1;
0 {+ w- Q+ t* J) ~# q  str=new char [size];
$ w+ {) s1 Z8 D. k  strcpy(str,tmp);
1 T- n1 N1 B+ U  return size-1;
4 A% ~; _0 ]7 N! t; w, H }
. t& ^  D& L/ y6 G$ ]+ D else
+ e7 F1 u+ m  A8 u5 b7 d3 Y) i  return -1;
- o# ?! Y! D# G" p}
' j/ o% u: B# s; Mint String::Rs()
: S; V2 w0 B* r/ n{
9 C& N' z+ B+ s; { char tmp[256],c;
int i=0;
* \5 t& {# @5 E while(in&gt;&gt;c)
. s# A2 H+ b9 D {
  if(c!='*')
  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
   break;
5 e6 V4 X& o  D6 L! w" `: m3 D }
if(i&gt;0)
{
  delete [] str;
  size=i+1;
: H5 s* B# g$ Y+ k2 V  str=new char[size];
  if(str==0)
   throw "error";
  for(i=0;i&lt;size-1;i++)
+ ~6 g2 n4 K0 H      str=tmp;  
  return size-1;
}
else
. v* W1 M* T% H- w; |  return -1;
}
void String:refix()
{
int m=Length();
' o5 v0 Z" L% K5 G# } delete [] pre;
pre=new int [m+1];
pre[1]=0;
# U7 x3 K. Z9 a6 j5 x int k=0;
8 K3 }  _. c, n6 s1 P+ H for(int i=2;i&lt;=m;i++)
{
% H* {0 _% O( k$ ^% D  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
   k=pre[k];
! C; m6 V4 Q" Z3 f         if(*(str+i-1)==*(str+k))
% P, U0 V- C+ x, p* a    pre=++k;
   else
    pre=0;
}
0 ?. Z' k4 Z# l& Y& J  @& a}
void String::ModifiedPrefix()
{
* D# M" a0 a4 j6 { int *f;
. }3 e9 a# o- O; q) t: p int m=Length();
f=new int[m+1];
Prefix();
% M3 [4 n$ s4 T+ A7 }, D. |8 ~ for(int i=1;i&lt;=m;i++)
! T5 x3 h, T- A- ], H$ E {
$ p$ S  y6 B5 S! f/ w* [4 ~    f=pre;
4 a" R5 f" c5 D* H8 ?, Z7 G }
9 y+ S& o! a7 G5 S1 X. R5 K7 O, O for(i=1;i&lt;m;i++)
{
  int k=f;
7 ]! ]! `( a, u5 a2 A2 o  if((k==0)||(*(str+i)!=*(str+k)))
   pre=k;
+ g7 C% a* c+ O$ \0 j. H3 x  else
   pre=pre[k];
}
" y; \( o$ V0 Z. H$ S! k delete []f;
}
; `5 }& x& E* y4 P" P& rint String::Match(int i,String&amp; t)
{
6 X; B7 C* @0 f2 ?1 _; E  R int j=0;
8 r+ Y( x2 h9 {1 N! p$ i( f" x int n=Length(),m=t.Length();
. l8 C+ i* q; H* m. {' [! ~ t.ModifiedPrefix();
, ^3 ?6 z) B( K while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
* F) @0 g  C+ n/ _7 Y  {
   i++;
7 S) `) S6 U. w% i  \" X& u2 j' E   j++;
4 n. u% e- s9 N& Y  }
( Y& m6 r5 i9 V$ ?! c( w: L$ M% s& }8 d  else
   if(j==0)
        i++;
- i" ^4 j% s( L2 r  ?0 x) O      else
    j=t.pre[j];
  if(j&lt;m)
$ t' X. v$ r1 M   return 0;
  else
   return i-1;
( F: M& Q' d: N$ y}
int main()
{
8 g9 O0 A) i! i- h9 {; c# {( W0 B if(in.fail())
4 u$ b; i- ?% w- b {
  cout&lt;&lt;"the input.txt is not exist!";
9 U- n; h" {3 a  exit(1);}
int i=1;
& b7 Q5 x8 i( | String s,t;
5 N5 g1 d) M9 R  p6 c s.ReadString();
while(t.Rs()+1)
{
  i=s.Match(i,t);
  if(!i)
! s2 k$ M3 |% K0 D+ {8 Y" p3 Z! E  {
. T4 ?) E6 z7 j7 b7 L& g5 d      out&lt;&lt;"No"&lt;&lt;endl;
! Q: w+ }2 _! |3 u9 T+ ^   break;
2 O. X5 z% |: ?3 }  }
}
9 I1 C; T% f3 C' P if(i)
' b. f! _# J2 r  out&lt;&lt;"Yes"&lt;&lt;endl;
return 0;
}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看