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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
/ j& e' N/ C0 t+ _class String
0 W8 c  z7 O  k; \& |$ @{
  public:
  w$ e! ^2 P9 a# |/ l* m String(char *s="");
String(const String&amp; s);
& ~- U; ?& B9 R/ S. B- o ~String();
int Length() const;
int ReadString();
2 C: ?, F& Z5 ^) @ int Rs();
void Prefix();
  C$ u( K7 u+ y) i% ~4 Y* u void ModifiedPrefix();
, Z* i9 I3 R# y9 S int Match(int i,String&amp; t);
  private:
   char *str;
   int *pre;
   int size;
};
String::String(char *s)
{
size=strlen(s)+1;
str=new char[size];
% d7 n8 [0 {0 b/ k! z: U+ F if(str==0)
8 R1 f9 t$ _$ `% s  throw "error";
strcpy(str,s);
pre=new int[size];
" e) V8 W8 D5 ~7 m$ R if(pre==0)
; d' t$ H: x! h5 n3 v) Z' y  throw "error";
. E5 D& x, R# i# T! z}
String::String(const String&amp; s)
{
) V* ?: c. W1 W) N* M4 j5 s9 s5 v size=s.size;
str=new char [size];
if(str==0)
. K2 b  x- _" p0 f/ k4 ]  throw "error";
- s+ |7 S3 _7 G) T) l5 j strcpy(str,s.str);
pre=new int [size];
+ I7 E, I& L$ j7 H4 W if(pre==0)
3 c- j, c  l- `; u$ _( B5 j  throw "error";
}
8 [2 ?# D7 J9 Y$ y4 U1 o9 aString::~String()
{
delete [] str;
$ b: {1 _$ w% W  N+ a! ] delete [] pre;
0 s. Y0 u8 Y3 z9 ]! U; i}
. w& `+ Z5 t3 H6 u" z1 J) U& I4 pint String:ength() const
& U& p" F2 o# p4 u) T. k. J% K{
return size-1;
/ D) M1 z* K" G3 H0 a2 {}
) f0 R0 U9 i; Q& M: h, a; m4 v& Mint String::ReadString()
3 o- \$ K5 |4 s/ g9 R" y/ }* i/ B{
" z3 Q/ g: V; @0 G char tmp[256];
    if(in&gt;&gt;tmp)
{
1 h8 @# l- m: W3 p% g7 K& z  delete [] str;
  size=strlen(tmp)+1;
  str=new char [size];
  strcpy(str,tmp);
6 T) ^. e' X( m* f0 S  return size-1;
) C+ X/ a* E& Q' u2 r. `) f% B2 W }
else
  return -1;
0 p. Y& l. U. j8 H$ x" R4 |}
int String::Rs()
$ H; H: m: K; }* m4 d5 I{
char tmp[256],c;
int i=0;
0 w1 j9 v3 \7 p+ @+ j* K0 w8 X while(in&gt;&gt;c)
) R/ ]1 d$ i2 P: p0 h4 B& y {
2 b  H' J3 f# B0 V  if(c!='*')
# t. c3 D4 C  u1 k0 o' [- Q3 B: x  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
   break;
- r7 l1 s7 |. L: N2 y( A }
if(i&gt;0)
3 _2 T! l' H* y: P+ O1 \ {
2 P2 s6 L$ m6 O! w' c$ i1 W0 ~  delete [] str;
  size=i+1;
  str=new char[size];
# u- Z# Q  ^- |) _0 c1 F; n: G  if(str==0)
9 a- O" _; f' D4 x/ B   throw "error";
  for(i=0;i&lt;size-1;i++)
      str=tmp;  
  return size-1;
}
& g* C* L2 a) K% ~8 C2 m5 | else
  return -1;
) e# x# X3 J" p4 ^* G: y$ L}
void String:refix()
{
9 i5 A, q* t* F# T# P  F int m=Length();
delete [] pre;
5 i/ i$ {/ ~# l6 H7 p# r" ^ pre=new int [m+1];
  R( K2 V) \" B$ _, f pre[1]=0;
int k=0;
for(int i=2;i&lt;=m;i++)
, e7 Y( s5 k3 l: ^$ s {
. p$ b/ e$ E" x" r8 w% i7 d! v  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
  n% j5 h6 e2 R7 ^1 L   k=pre[k];
; ~) h& Z0 c# g6 s6 H         if(*(str+i-1)==*(str+k))
5 l% K- G; j( w, y; E, @5 S    pre=++k;
   else
% O/ B. U3 p: [3 J    pre=0;
. a+ b, v4 N- x2 s2 p }
}
void String::ModifiedPrefix()
{
int *f;
int m=Length();
f=new int[m+1];
3 `! L" _1 S) M: D$ m Prefix();
for(int i=1;i&lt;=m;i++)
{
    f=pre;
}
for(i=1;i&lt;m;i++)
# G- U* v% f9 Q' @8 F# y6 H {
  int k=f;
& l  w$ Q% {/ A. F2 W  if((k==0)||(*(str+i)!=*(str+k)))
   pre=k;
  else
2 j: I7 m1 K; M+ i* h8 E   pre=pre[k];
}
delete []f;
  x$ ^' A& q/ {" B/ x2 a/ q1 Z}
int String::Match(int i,String&amp; t)
; i& l6 Q1 S8 f. a, g0 Y6 R{
int j=0;
int n=Length(),m=t.Length();
2 L  v; g# t9 r, ^; j8 ~ t.ModifiedPrefix();
) t! m* V1 `9 X5 |3 j while((i&lt;=n)&amp;&amp;(j&lt;m))
  if(str[i-1]==t.str[j])
  {
! t! @+ P# Y7 y- Q0 C& P   i++;
2 P1 S! o/ x& A. f: H) C   j++;
4 G. X$ ?" V, i2 j* H7 F  }
  else
   if(j==0)
/ V% b# [& r2 u. N' G# b0 p        i++;
. x. u5 i6 P$ R: S& a2 H5 Z      else
2 d. b! I% {8 a1 w/ b    j=t.pre[j];
  if(j&lt;m)
   return 0;
  else
   return i-1;
}
int main()
{
if(in.fail())
{
" t8 J: A. O% ]0 S/ o: j  cout&lt;&lt;"the input.txt is not exist!";
2 A7 i+ ~5 J# Z( K  exit(1);}
int i=1;
String s,t;
) d$ P& u( c( G7 J5 e6 ]" j s.ReadString();
while(t.Rs()+1)
{
  i=s.Match(i,t);
  if(!i)
  {
9 J3 ?# K& d) n# x, |/ m! ~$ }      out&lt;&lt;"No"&lt;&lt;endl;
; p& E- B7 G* |   break;
. k. ^- L9 ]! ]' G/ p( {  }
}
if(i)
8 k/ J- N6 b3 F8 C9 A' K; v9 ?  out&lt;&lt;"Yes"&lt;&lt;endl;
4 Z, m5 u* q$ l4 k$ Z) y2 J& b7 ~ return 0;
* y, T4 s9 L  C) y! m}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看