- 在线时间
- 0 小时
- 最后登录
- 2005-4-22
- 注册时间
- 2005-4-22
- 听众数
- 2
- 收听数
- 0
- 能力
- 0 分
- 体力
- 72 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 26
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 7
- 主题
- 2
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   22.11% 该用户从未签到
 |
< >很经典的一道问题,我想大家应该都会,我这次只是想帮助那些还不是很懂得人,还是一样附上解题报告和源代码。觉得好的就顶,主要是用模式串来解决。</P>+ J$ m8 X8 {; A3 x& \
< >[[/hide]</P>#include <iostream>
1 k+ W7 R% t8 _$ V9 i4 y! l#include <fstream>
$ s# K1 T8 a) h. fusing namespace std;
' D: U) O0 C9 i/ J qifstream in("input.txt"); x7 D* Q; O6 @4 F
ofstream out("output.txt");
) }% j! [ i5 i4 D A$ C# d5 D+ Hclass String
# h' F1 e3 w# S ?' ^1 L+ O{$ g1 b$ ~: ]' B; z: y. m- N
public:
: _5 C& _1 g% I$ G3 i6 H) J5 ~# l String(char *s="");
: C- E' U3 }, P' h String(const String& s);( N) G6 P! p9 g/ T
~String();
) m0 _% J4 v# ~' L8 A& B$ Y int Length() const;
) v+ d: V, c) v+ O& E9 K* b int ReadString();! B9 Q) l3 q+ Z1 e H' v7 j( K
int Rs();
2 ^+ F& n8 A6 r6 |7 b) I- h void Prefix();- C, X& v$ `$ a
void ModifiedPrefix();' E: f B$ u) n9 {
int Match(int i,String& t);
4 q0 h7 m$ `1 q, X/ A private:
0 l( h4 d7 Q8 Q0 l% Q8 t1 \ r# y char *str;
6 L- i# q' ~2 n- ?3 b0 n( @ int *pre;
5 `/ d- w4 w& j/ U: \' p int size;
7 y4 ~' ]5 u8 B/ @) i};
- T' Y4 s9 F) L! k! WString::String(char *s)
& h. U* l; j% t/ I2 ]{7 F" |4 a8 u& V7 B0 o b, Y: P
size=strlen(s)+1;! V3 K: T& ^. N& O/ L5 z9 r
str=new char[size];
+ b3 D% b( S' w) Y) [1 x if(str==0)2 o/ r" z. s+ B
throw "error";/ K. N6 L# N4 B: d3 T. Y
strcpy(str,s);! Y9 Q1 l" Z9 @" I
pre=new int[size];. r) q% W3 n; _9 p( T6 K3 d
if(pre==0)
6 [( I" L7 O- ~" ]6 P6 E throw "error";
& n& N! W! d# P& @# N}
: L3 u# F; x6 x. R: dString::String(const String& s)6 A! d3 o! { U# U& p6 N& T
{8 X; Q J' c0 ^. i& Q/ }
size=s.size;: P0 d2 m, X6 t$ n0 C
str=new char [size];
% A U: x! I* F+ c if(str==0)( z+ v" W/ z) A7 Q
throw "error";/ h7 P' g" Z ~# Z. z
strcpy(str,s.str);, C9 `3 a4 H8 r9 [( J
pre=new int [size];
: C8 z& j. U4 d6 k# f if(pre==0)5 I& Y7 b/ e' l$ v. w- f+ z
throw "error";1 g. y3 O0 z( e' w+ M6 j
}+ L7 D N6 k8 E; f8 ]
String::~String()
1 l2 @: Z) C$ ^4 x# }$ ?{2 z+ V C+ l( L9 r% I; j& k
delete [] str;2 W! G- {7 ]# _+ b
delete [] pre;
1 G* I% e; ]$ M+ r+ g7 G}
- t* i3 o+ Y' h7 ~int String: ength() const
: J/ i! p5 k8 Y a, M& d7 {+ U{* g1 r& T8 q6 k5 O U6 i7 R5 j
return size-1;
3 g1 m+ N# r! A7 ~* f}
* g* T7 i0 Q6 K3 v# H+ |6 }int String::ReadString()
, T/ p6 E- Y% ~- v6 |{" n, j& u9 g' U) X& G, v
char tmp[256];& C8 L2 x: X/ H4 d" @* h9 O" S$ i
if(in>>tmp)
% ?1 c' R$ X6 Q {
4 y/ b2 v0 u1 c: d9 H4 `9 g delete [] str;
/ ?/ J. |/ i9 a size=strlen(tmp)+1;9 G6 _5 S! _( _4 T
str=new char [size];
2 A3 e x3 E. Z0 k/ A- a' p strcpy(str,tmp);2 L2 P4 W8 I. L8 B
return size-1;
& j9 W: I! t* \. N D: _ }
2 x7 l# E! h0 ~4 Z% _ else
/ u* W, _. ^6 ~0 V return -1;/ B4 i% I! z' t
}
9 A& `" T* p) p' Y; e, eint String::Rs()0 A+ |5 p9 X3 v" `
{ ~2 z W; {" k/ k5 V8 {4 M0 B/ I
char tmp[256],c;) M+ T+ `* a8 k9 F1 o0 |! j& T
int i=0;
4 \8 c+ o" b2 x" h# R, y while(in>>c)# F" d+ I+ U6 r2 v! ~
{& y* a) _0 v6 D9 Y4 [: F9 b2 E
if(c!='*')
* y0 `* W p0 K) ?- {$ e tmp[i++]=c;+ h3 V6 g. i: D! w
else if(c=='*'&&i>0)
& `8 x: H/ ~0 C# x1 p d5 Z break; V2 H( @! a; S" ? }: `
}' y0 ]: W* v3 a( M" Y( X: p' u5 p
if(i>0)9 u- j! F# b4 \4 T
{
' i% q' f5 T# t5 K! I2 p delete [] str;
$ E1 e. R0 k7 y6 k size=i+1;
- H# B w# w# k: N" _ str=new char[size];& O8 H% s7 M+ m7 y% c
if(str==0); D9 L$ J1 v% l3 L0 ^( O
throw "error";4 b; x* t6 x( r
for(i=0;i<size-1;i++)' I5 x& u5 Y, T6 a- b6 `7 ?
str=tmp;
- a9 F: @2 c' d. { return size-1;6 V3 w$ Z9 J$ n$ H7 A- G8 y
}
. S3 n3 Y2 {$ \9 D m* f/ ? else
9 x2 g8 o+ i& M return -1;
: |/ J+ h4 l/ d1 q}
3 c! o& k- V8 j, W" M5 M* Pvoid String: refix()
f0 N/ t# v3 R" D; i! X1 O{5 K9 Q, r' H+ t) h+ p
int m=Length();
* b; O7 y7 q0 q' w delete [] pre;
k5 l8 b- p4 A) c# V0 R9 u; ~ pre=new int [m+1];2 |8 ^4 ?( Q' [0 o, |: c8 m2 v
pre[1]=0;
$ Y/ S+ Q9 F$ D' E T! q6 N: G int k=0;
2 X0 a4 M e' {; X! C for(int i=2;i<=m;i++)
5 N5 y: n. ?2 v4 C% t {
g. @$ Y: Q2 v4 @- s: f" [ while((*(str+i-1)!=*(str+k))&&(k>0))3 v I( W; Q7 h7 S* a
k=pre[k];
9 t3 f1 H6 a0 w* k) X if(*(str+i-1)==*(str+k)): M4 Z b: M6 f4 l! Q
pre=++k;+ C0 }- @! P7 B5 [1 Q! P
else
4 N" H8 ?$ W8 z" W pre=0;8 K5 H" X, C- a$ ?$ u
}4 o7 f% U0 ^+ i, f' j( F- a( T
}: m6 k! v: D9 l' f j& ~. o4 {8 x
void String::ModifiedPrefix()
; _- F; g, s' [$ A4 M% f T; @+ D% f{ C6 _! B9 e: v6 E& s9 b3 o; W
int *f;
, |9 d- W2 s% B/ v e! @( J int m=Length();/ p+ W3 d( |# r6 r% D* ~- z
f=new int[m+1];
0 e. }9 i# k) t6 I- g2 H Prefix();$ P( c8 `! C+ a, o6 x
for(int i=1;i<=m;i++)
4 x [: ]( |5 t8 j {4 Y7 l8 d, ^- X# E) a/ m# ~
f=pre;- {$ T; b+ u5 B( T% l7 G l
}6 ?2 l8 G! A' q' q- j+ X$ r
for(i=1;i<m;i++)1 G9 f* k! G! G+ ~, M! @3 \& K! U
{
+ { V6 C: [6 c J# E( ~ int k=f;
6 X" F. z+ X4 H* X! P if((k==0)||(*(str+i)!=*(str+k)))
+ v6 a8 a/ j+ d: A5 y pre=k;
" r) s7 ~6 T' V! f* P else # t( }+ Q1 t2 Z0 F! t6 D
pre=pre[k];! z% }9 P* w, {( G ?. ?2 v
}
9 J; r9 K3 l9 j6 j+ Z( N+ J/ v) U delete []f;8 e% M T. M! [9 Z$ W$ w
}
' ^* n; d2 ~3 T' b K$ uint String::Match(int i,String& t); _( Q$ f& ^* O; F$ J9 a
{% c+ H' _6 r( U* I, I/ r
int j=0;
7 S6 R. B, N! f p8 i, \# A int n=Length(),m=t.Length();; V, I4 x5 ?8 F8 z
t.ModifiedPrefix();; s! E! r2 {7 y* S! E
while((i<=n)&&(j<m))
8 c1 g5 h" S0 b" ] if(str[i-1]==t.str[j])( f9 |7 d3 ^+ J
{- ^: k; `# r* e
i++; m" p5 |2 w2 N8 M- k8 Q' H9 C9 R5 J
j++;1 z6 P2 r$ x6 a6 m) z, Q2 c3 e7 p
}' Q C1 N0 K7 Y4 _; e
else
2 z/ { A, [3 U& v0 K, v3 X& Q if(j==0): m; V( ~; T, ? h
i++;( [6 ~' ^! c; E+ L) u
else 6 D7 ^, e, B, h4 E! R( J, Y0 [
j=t.pre[j];( ^. @9 H8 w8 Z
if(j<m)) J1 k4 J0 m( ?1 i! g
return 0;
! P( i- _' m' s ^ else : j8 s3 U6 Q" c9 f% M- w% Y
return i-1;
) t+ Y: x+ a9 m; Y: |! x# P}7 ^3 `4 _+ h% e# K
int main()
5 e- `0 P. F9 Y; ?/ F3 Q, Z5 I# N{! }3 B4 Z. | {0 b* p
if(in.fail())
b: K/ ]: u5 w" s+ {; `7 { {
3 d, ~6 Y5 I" ]! w9 O% m9 g: b; ?6 E2 M; X cout<<"the input.txt is not exist!";
% j' K' |1 q* w& T3 i exit(1);}
9 T3 H" B9 Q9 O. }) L, K# g6 G) S int i=1;
$ U! ?: u F; ?6 N3 w* Q String s,t;7 i' o0 i B2 \3 ^
s.ReadString();
2 c4 @) g- J. ]8 h- x# } while(t.Rs()+1)
0 P7 ^% p1 y8 h4 `; Z( J2 V {6 S& h3 Y- C7 R" `& X# j9 g
i=s.Match(i,t);/ I1 Q0 O( [, K: a9 }2 r9 k
if(!i). i, c8 ?* H: Q. [3 _: B8 y1 P$ P
{
6 Z) Y: N3 `1 `6 @. h6 ~ out<<"No"<<endl;
( J6 i* V1 P% T- O( H break;
g) u% n8 k$ w: B O& } }
: U/ s+ U- B4 ?- S }' b* O N$ X! j& i j' v7 D F
if(i); y5 U9 ?! r$ i! e* `
out<<"Yes"<<endl;
( l0 e5 m2 S! d M$ y return 0;
$ f( x( q5 L2 t. o} |
zan
|