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

lynnyan

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

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

[/hide]</P>#include &lt;iostream&gt;
4 Q- L. J! l4 ]! s) X* Q  @#include &lt;fstream&gt;
+ `) \( L& e( \- \, C/ ~using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
; F" \2 y% n6 s$ @+ w' Sclass String
8 p0 b' ~) d4 r, ?* M{
% J8 z7 ]$ x: [; ~1 E- u  [  public:
5 K% A6 t  q/ k) V' ` String(char *s="");
! Q" O) Y0 K1 {/ j) ?0 E String(const String&amp; s);
~String();
* `+ Y9 A4 A$ d9 T# M0 Q9 G int Length() const;
1 b! u, Q- F; E2 t& W int ReadString();
int Rs();
void Prefix();
2 E6 U7 K" R  Y( u' { void ModifiedPrefix();
5 v5 h; R& O& y% R9 ] int Match(int i,String&amp; t);
, ?* d& x1 Q) F- P( B# T  private:
   char *str;
   int *pre;
! j; t9 F3 z2 ?   int size;
# z/ R# \3 X1 |2 W$ X};
3 I5 U* D. Q' BString::String(char *s)
{
# V8 m$ b* F0 I size=strlen(s)+1;
" z9 P. k. u" C( R& O* ]/ N: w str=new char[size];
$ i3 Y3 W# w1 t! v, B4 ` if(str==0)
  throw "error";
! S, Q; {2 X! r4 j8 W; w- x  w strcpy(str,s);
pre=new int[size];
- H+ N2 H* f) ?$ d. D4 j if(pre==0)
  throw "error";
6 I5 Z1 I% I! v) d* N8 g}
4 t6 [& e- E- H+ @String::String(const String&amp; s)
+ W. b: X( W+ N8 ~6 i{
* V( I' K" t! S size=s.size;
7 ?! X" E6 L" S6 b6 a8 a8 t4 h str=new char [size];
if(str==0)
  throw "error";
strcpy(str,s.str);
pre=new int [size];
if(pre==0)
/ c# b* M' M( o/ ?3 ~  throw "error";
}
8 u; k; Q4 H  ?0 h- v1 t+ H- S5 OString::~String()
{
delete [] str;
delete [] pre;
}
int String:ength() const
5 T3 g) y4 ~7 k{
return size-1;
}
int String::ReadString()
{
char tmp[256];
    if(in&gt;&gt;tmp)
{
9 b# s0 }! k- y2 @  V% w  delete [] str;
9 u. ~5 m" o3 z* M' |7 R1 w  size=strlen(tmp)+1;
  str=new char [size];
  strcpy(str,tmp);
  return size-1;
}
else
  return -1;
9 z! \6 F+ D0 _2 M7 s6 {: E8 J}
int String::Rs()
{
char tmp[256],c;
) C9 l0 n9 T0 F' t0 N int i=0;
2 s6 W; F$ O* y8 t$ m while(in&gt;&gt;c)
{
  if(c!='*')
) h* c# a. F1 b9 T! j! ^  tmp[i++]=c;
  else if(c=='*'&amp;&amp;i&gt;0)
   break;
; l% v% ^8 ?% P9 O/ Y) ~  z4 @5 b }
if(i&gt;0)
+ s8 x6 F+ M- `( M {
, ]5 H- X9 ~" n" g  A9 ^( g  delete [] str;
  size=i+1;
2 R' G6 c5 o8 m  str=new char[size];
  if(str==0)
+ X% h" O' Y9 H7 T( O2 _9 s   throw "error";
1 w) B3 U! `0 e6 S9 C  l  for(i=0;i&lt;size-1;i++)
: I  D2 E% P& f      str=tmp;  
  return size-1;
}
else
  return -1;
* l# @8 ^! o. i% O* d}
- s8 `3 V  _0 {6 n+ f1 ~, C' Rvoid String:refix()
9 G9 L- C0 w4 S; l{
7 i, A+ M0 i# {: j  [/ B int m=Length();
+ h8 _  L7 Y- x+ s delete [] pre;
pre=new int [m+1];
pre[1]=0;
int k=0;
/ p+ L# D" g, m5 U for(int i=2;i&lt;=m;i++)
{
  while((*(str+i-1)!=*(str+k))&amp;&amp;(k&gt;0))
& ], p/ _" A5 X) \. D% k   k=pre[k];
6 }, S: u* c) ?; J# |+ H         if(*(str+i-1)==*(str+k))
6 m( u% P& W- S6 Y% w) P* W    pre=++k;
# v1 c* J' p& j5 q   else
    pre=0;
}
# P' x2 m7 _4 W6 e}
void String::ModifiedPrefix()
; D' b+ p" N/ x2 `{
int *f;
int m=Length();
f=new int[m+1];
* q$ \7 ?$ Y- G& H Prefix();
4 a& m; e8 S. _' P7 ]; j; m for(int i=1;i&lt;=m;i++)
) I* n/ R3 V) |! I+ M {
9 d; D( w- y6 R% b2 {/ {    f=pre;
}
+ T/ @4 `3 F/ k: F+ n( M( ^ for(i=1;i&lt;m;i++)
{
  int k=f;
  if((k==0)||(*(str+i)!=*(str+k)))
  q& R$ k5 H6 D# d   pre=k;
  else
   pre=pre[k];
}
delete []f;
' J& p: y8 @1 c}
8 ?( x# d. n8 dint String::Match(int i,String&amp; t)
{
int j=0;
int n=Length(),m=t.Length();
t.ModifiedPrefix();
while((i&lt;=n)&amp;&amp;(j&lt;m))
8 a/ {) B! z) h  if(str[i-1]==t.str[j])
( P% x+ Z7 q0 @* G, Y! `  {
9 D1 }' i, a) n; H4 Z/ {) {   i++;
" R, ^9 W, u) I- ^/ Y   j++;
+ c) L% H7 I. ^  }
  else
1 ~8 d+ j- e1 `   if(j==0)
        i++;
      else
* ?% u2 S3 f1 P4 d# g    j=t.pre[j];
  if(j&lt;m)
1 d; H: X( |" n: Q7 m/ n  \   return 0;
7 L' W$ D5 z2 [3 i7 }% F7 N  else
   return i-1;
. W7 y: T; L- `: I; u% B& K}
int main()
! ~" U. [2 q! ~) h) q{
if(in.fail())
, @7 j4 B2 |+ [7 {) { {
$ g2 G, K! i& Q# R$ u  cout&lt;&lt;"the input.txt is not exist!";
  exit(1);}
7 Q3 M# M& J. I0 q8 H& K- W, @ int i=1;
String s,t;
4 J: g! B8 V5 Q" r s.ReadString();
while(t.Rs()+1)
- f  [' E/ T; k* V1 Z1 u# C4 B2 \! x {
1 N/ l/ f, N% K6 L; F  i=s.Match(i,t);
  if(!i)
; L, f7 G" q) x9 w" A9 ?0 c( v2 O8 K  {
, Z$ p  E# c) ]6 a) h/ y3 I      out&lt;&lt;"No"&lt;&lt;endl;
   break;
  }
}
if(i)
  out&lt;&lt;"Yes"&lt;&lt;endl;
return 0;
}

zidance

看看啊

sgnswb

顶

ari0101

谢谢

hyacinth13

<p>谢啦~~</p>

zhaoyunfei1126

好吧[em03]

ottiou

看看看看看看看看