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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
#include &lt;fstream&gt;
using namespace std;
5 a) `1 Q; s/ C# R* j2 B4 I$ vifstream in("input.txt");
ofstream out("output.txt");
- N* w1 M0 S' J8 ?9 Fclass String
{
  public:
String(char *s="");
String(const String&amp; s);
  j8 A8 \8 w- J  N+ X! [' H ~String();
  {, O1 j4 `) M* s4 E0 x4 @ int Length() const;
0 p/ e7 s" d* Q8 u$ ?$ |5 m% q% p2 y int ReadString();
& f6 K7 ]. W8 t int Rs();
void Prefix();
void ModifiedPrefix();
3 Y) a! y: O- [4 B% | int Match(int i,String&amp; t);
" k* O: T/ @/ P" a. h' `2 K* P% G  private:
& H9 B! q, R3 M+ |+ `& ^  r4 q0 g   char *str;
' H' n4 c' a( c. ?" m' E; j7 [   int *pre;
( p7 t+ B1 Q! n   int size;
};
String::String(char *s)
3 Q4 M4 }  ^% P{
" d' e: t+ j) Q; v" h size=strlen(s)+1;
str=new char[size];
if(str==0)
  throw "error";
" P0 a* @' J1 ?9 x! \0 @; {: R strcpy(str,s);
, K6 {- {+ v7 O  A3 @3 I pre=new int[size];
+ d1 y( a2 O! H9 B/ b1 E! p7 E if(pre==0)
& H- W0 B, |7 F$ A! \  throw "error";
; ~# x( K# @: ^! ^9 H# b- ]}
String::String(const String&amp; s)
, v0 |, V' X- I! b{
2 s8 `% w: j0 r! H' t5 J size=s.size;
str=new char [size];
if(str==0)
  throw "error";
strcpy(str,s.str);
( L/ N3 y) [! Y pre=new int [size];
* A( J  l$ n2 p3 N9 Y  a% B8 @ if(pre==0)
  q+ N; u* W* m) I7 s: S  throw "error";
$ J/ q. F9 E1 y}
String::~String()
{
delete [] str;
$ R5 M! k" b) A3 }" E* c8 K delete [] pre;
* |1 u  t+ Y: _$ Q}
' Z# g1 q- ]$ H* D2 Dint String:ength() const
8 g9 F, G7 X4 c3 B- `{
$ M; d: ~) A7 H$ V5 K" j return size-1;
- z7 W$ G4 `5 v+ B( n3 Q}
int String::ReadString()
+ Y. X9 l' ]: u0 x{
char tmp[256];
# G3 [; T0 @3 @9 W4 h    if(in&gt;&gt;tmp)
{
  delete [] str;
  size=strlen(tmp)+1;
4 Q! G1 T: A  K  str=new char [size];
* M  M/ d2 }; i! _6 e6 w  strcpy(str,tmp);
  return size-1;
}
else
7 |4 W4 K5 @) Q  return -1;
}
int String::Rs()
{
char tmp[256],c;
- v, H! S+ Q6 ^! A int i=0;
while(in&gt;&gt;c)
8 h7 n2 v* ]9 a- V: B  q4 H1 J6 X {
  if(c!='*')
  tmp[i++]=c;
3 O1 z( g7 `- \1 _& r9 r3 a  else if(c=='*'&amp;&amp;i&gt;0)
   break;
/ ]! N" h7 O" n }
if(i&gt;0)
. Q8 {! J3 M/ ^' Y4 ^9 m {
  delete [] str;
( |; B0 s/ X( R5 p  size=i+1;
  str=new char[size];
  if(str==0)
3 z1 J- L8 h) n- ^! t) T   throw "error";
  for(i=0;i&lt;size-1;i++)
      str=tmp;  
, e7 F, ^. ^7 w* i$ u9 ]' y6 k  return size-1;
+ I/ E( h- e, n# |; q# E6 L }
' }- D: C8 A, Q! x. x$ d/ A else
* P7 ]2 P6 K' h6 ?5 U8 {$ h( M% v  return -1;
3 y9 I3 ?$ u3 ^- P}
! p# ?! ?3 ~5 O6 Bvoid String:refix()
{
+ o5 P7 ^% D0 S7 ^# `  b int m=Length();
delete [] pre;
pre=new int [m+1];
. h$ D0 q0 O/ C0 a, R pre[1]=0;
int k=0;
% m0 ^5 v# c4 o5 w7 a* s for(int i=2;i&lt;=m;i++)
5 e% M8 c  C8 M3 v+ K {
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
+ @# E6 N1 I7 b4 [   k=pre[k];
; Z. }& z" X- y8 O# u         if(*(str+i-1)==*(str+k))
    pre=++k;
   else
    pre=0;
0 D" w! E8 l! z/ C7 l }
8 T, N2 W$ {; K, i. h, ~}
: s$ G& r2 a! @9 Nvoid String::ModifiedPrefix()
{
% f$ Y0 i3 D# D! Q int *f;
1 A  T% F4 D, a int m=Length();
f=new int[m+1];
Prefix();
! ~6 ~1 I! d: i' d3 ] for(int i=1;i&lt;=m;i++)
& P8 V0 P7 n2 u  f' B' T {
* ?) R5 O6 z7 `: h9 Y    f=pre;
! ~" Y' ]5 u* Q }
4 `! c! X% Q4 f( E for(i=1;i&lt;m;i++)
{
  int k=f;
, ?( @  N, ?& ]* ]  z2 a  if((k==0)||(*(str+i)!=*(str+k)))
- `2 q1 n9 b/ q2 e0 k& i6 N   pre=k;
/ |9 [  b* E" A8 \5 V7 h  else
" g; W) b3 O2 ~7 p, N   pre=pre[k];
& |: ]9 \, J0 c; k7 r7 q }
delete []f;
* z- R& |' p* \. v; N5 Q}
int String::Match(int i,String&amp; t)
5 D, P6 A( U/ O6 }. w# Z- p{
/ N+ p2 ~( ]3 S6 ] int j=0;
* g3 H; R) P3 ]+ d; b3 l5 d int n=Length(),m=t.Length();
( T. S7 S: _8 r+ A( F t.ModifiedPrefix();
" D8 a! g1 q. @" q- q4 P while((i&lt;=n)&amp;&amp;(j&lt;m))
% I8 a9 q2 @0 j0 Q8 V) {9 V6 N/ k) T  if(str[i-1]==t.str[j])
  {
3 Z- {/ `$ x9 r+ b. q! Z   i++;
   j++;
  }
  else
   if(j==0)
9 r5 `" O1 U& t" h# p        i++;
      else
    j=t.pre[j];
+ a6 j0 j1 e! N  R1 d  q  if(j&lt;m)
3 t6 K( R5 T$ _8 S% K   return 0;
2 B  L) Z% }( x3 R( P9 Q  else
   return i-1;
# }/ b" R7 s6 K9 X/ {/ k}
  r. d3 h* Z! X; ]: X5 P6 kint main()
+ T# q! p7 u* i{
if(in.fail())
{
% s) M* t$ S( p0 V  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
int i=1;
String s,t;
s.ReadString();
while(t.Rs()+1)
3 {+ |& T- [9 }. Q: I {
4 ~" H: Q; L9 e5 g0 `2 g  i=s.Match(i,t);
  if(!i)
  {
- }, P# h( l8 D* |      out&lt;&lt;"No"&lt;&lt;endl;
   break;
  }
}
2 d! q2 e8 U; z/ ?9 g7 S if(i)
5 u& u$ r2 Y! j# f  out&lt;&lt;"Yes"&lt;&lt;endl;
3 [- y0 u$ ~, l) Y% \, F return 0;
* C9 t9 [3 i" d9 W; ~: @/ \}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看