- 在线时间
- 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>
' R) ]8 c; x5 l- S" ^" ^6 N< >[[/hide]</P>#include <iostream>$ z( {0 B2 o# b1 O A1 L4 n1 g: A$ D# D
#include <fstream>2 E% n7 g4 G# |5 ?0 x8 v% L# M, x- W7 P
using namespace std;
5 `: ~6 r5 e; o" o$ C# g9 oifstream in("input.txt");
* H- p: l6 c5 R8 n# i* a7 [# Y, ~+ rofstream out("output.txt");
2 |/ E' M3 k7 N( u3 ~3 Xclass String% z V, }0 _0 C; |. P# U
{1 o% u2 u$ q. B" C0 u
public:
- T& Z) _8 M0 M3 l& }6 d' K! \ String(char *s="");
. J# s$ \( P. g String(const String& s);3 } I7 ^& O i4 K$ q/ |9 t" j
~String();
; z) m D- ^$ U' }* X' B1 e* M. _ int Length() const;
' W( Y) a% O( `8 b, ~ int ReadString();
$ r) j' ]$ E) s: \, w" ^ int Rs();; w% |8 ?' j# A' T& y1 y& a
void Prefix();
; v8 e. M0 u' I6 u void ModifiedPrefix(); r- B% f3 l$ E: M. I8 M
int Match(int i,String& t);# `, s" c* |! p% f7 w# R
private:
2 |+ a% Y2 _: T4 P9 E! x char *str;9 f* ^0 c7 b! m# U$ S4 a" t
int *pre;
3 L3 R4 S( s7 ]- K/ W; `/ R int size;& V! z( N0 C/ R, n7 N
};# I- _# i7 B- }- _
String::String(char *s), p. {4 k0 F) @& e
{
, ? g0 E5 p1 w w7 H size=strlen(s)+1;! b- J. |6 j! T7 C, m: Z4 d
str=new char[size];
% g4 d1 } x( z! U$ G if(str==0)
, F1 Y. P! x; O6 z6 i" X3 O. B6 Q throw "error";
) [3 u# j( ]3 o( P strcpy(str,s);1 Q* w, D! p% c8 @1 @3 N
pre=new int[size];
; i7 F8 f1 k- h! c! k; U9 ] if(pre==0)8 d7 t# M) ]+ W- |# F1 ] m0 X' P
throw "error";
& U( D2 c5 ?3 C9 U9 z6 H* E6 h}- J7 l. }! Q: i3 I' o" D
String::String(const String& s)% R$ P1 f% D8 i5 G! o) V* B9 M9 o
{. h$ a" e, W6 Q0 l, e. u
size=s.size;
5 y2 z0 V- _6 k0 Z* f$ m) M/ h6 H% u str=new char [size];
4 e" F. ]! i$ k& T+ Z9 s/ g if(str==0). ?5 J. { l" r* W+ o3 W1 ~
throw "error";) \2 a8 k4 ]. @! P+ H
strcpy(str,s.str);
- E0 @% H* I/ f s W pre=new int [size];+ T1 }. k! b3 Q9 D! r# ~+ F5 L4 M
if(pre==0)
" ?7 z- u( z3 m1 m/ V9 u6 u throw "error";3 x. p. z4 q' f! @$ }7 H4 \
}
) K; P- r2 o5 m+ ]) vString::~String()3 E! y) M8 l9 G0 E3 g" Z4 O* t( J
{/ s5 e' T; j, ^
delete [] str;' ?9 o" l+ y! N3 V3 N$ Z
delete [] pre;: ~) c3 V- F/ o
}# _9 ]9 R4 x/ C) Z6 w
int String: ength() const
( Y2 j/ S3 _8 e+ m( E& I: f$ h4 R{
8 V% f9 R' e/ l: U return size-1;% s. a- B. D4 [& s6 `* h& |- Q
}
% |1 x( W3 T3 \8 Z S8 K$ Uint String::ReadString()
: W! u0 B/ ?; q{
) N" l+ T: n" q; w' o8 D1 G char tmp[256];
0 Z% `6 f4 Z+ R( y, C0 T2 F if(in>>tmp)
" X6 e9 D5 ^+ M1 j3 g {6 E4 `' e1 b# ~
delete [] str;
7 [7 L- I* N F' ^8 J. v size=strlen(tmp)+1;
3 W# y- i' O) M. P str=new char [size];
- v- v. W; ~, F) K7 g+ Y# T4 Y strcpy(str,tmp);- E/ e0 ^1 c w1 t% x* _4 N
return size-1;
$ V) Y! q' Y7 Y6 P& ~7 w! [1 j }! l U f& z [; n% g) M! J
else4 Q2 n, _" {0 I6 f8 R7 e( m! Y
return -1;4 y9 n- I* o/ g2 T
}$ o$ F( E0 \6 f* ?8 a; r
int String::Rs()! @/ W: Z1 u1 |& W6 r7 \' X0 k1 m
{
8 G: C, G. |0 _2 k4 h7 a: O. d char tmp[256],c;
( H( z. w* c( K' { int i=0;
( P. x1 ^4 E% T while(in>>c)' j8 h; Y9 ~* R. i
{
. D3 p3 p8 B/ N, p5 e/ R if(c!='*')
" L: j) h6 G0 z" j- M- T$ @ Q tmp[i++]=c;
! c, M) _6 U6 J1 R! w' z else if(c=='*'&&i>0)
+ N2 J8 b2 {8 ^) m6 H) s break;! K" I" c! }" D
}
' N p* U6 Y9 z \ if(i>0)
3 N6 S4 Z- ?5 g; [; b0 Y3 X {
+ o" r4 T! l; x7 x6 \8 ] delete [] str;
" @8 k9 p5 R/ U size=i+1;
Y8 l, Z5 ~/ n/ Y- ^ str=new char[size];
. I8 V( b; `1 r2 \! G if(str==0)
, e1 j+ V" _! [2 x throw "error";0 O4 ?" U7 ?2 K' G9 ?6 r, z2 x4 D9 z3 B
for(i=0;i<size-1;i++)2 w5 V8 ?4 W; I
str=tmp; 9 c8 o" p6 M) L
return size-1;
$ ~2 q( H( `7 U }0 O, {: q- I0 u" i# T% `
else1 N2 f9 X3 V0 ?2 U, b4 h
return -1;
" C( n5 ?) Z- j) ?}
5 U2 `8 a) @& Y- _5 a9 q: w3 l2 ~void String: refix()0 O, j" ~8 v- ~+ b2 s/ W1 l" r
{
0 |7 {; M# l$ g/ a+ z7 P; ~1 Q) v int m=Length();+ ?+ ^& x$ e- J: G
delete [] pre;
0 [2 y4 `) s+ g3 c pre=new int [m+1];
% T* S6 i& y" W; K7 G. w6 N pre[1]=0;
; [# h+ Q' O4 [0 X int k=0;$ p5 l/ q, _" M: T& _$ ` U3 u! g- S
for(int i=2;i<=m;i++)5 X( C2 f: D( s. A
{
3 V8 o7 T: {, T while((*(str+i-1)!=*(str+k))&&(k>0))* i- i1 P& t& H1 }5 T& A7 R2 `7 B3 G
k=pre[k];1 C3 v! X3 Y3 G
if(*(str+i-1)==*(str+k))
/ H$ A' t$ R: A j' i pre=++k;. x' c3 n4 j R
else8 O* ^# V. k: d- H. E0 g7 E
pre=0;
) v5 \* R# G( ?1 i3 z m }
7 [ @ E- x3 |6 c3 U8 Q, n0 R! @}
' x1 [, ~" o% l6 s0 F0 P7 b' Ivoid String::ModifiedPrefix()3 l, u4 s! B1 V- L! i2 m1 ^
{
" q6 o; e- C* S3 R+ H$ R; L int *f;4 P! H, L0 M9 W0 ^
int m=Length();8 Y* n2 P- D3 v8 v4 D. s
f=new int[m+1];( e6 w" E& Z# I. `$ o
Prefix();
+ d* r# x2 t/ Q for(int i=1;i<=m;i++)" _. j- Y2 g2 K& ]! V
{" \$ B/ W+ d$ b2 n/ v; l) c: d
f=pre;
, o- s, [- ~$ A' Z) o }4 @, A6 G& N3 q' r$ a9 |9 y$ H
for(i=1;i<m;i++)
+ ^/ U$ p0 V6 o% a: [2 ]8 ^ A {
4 J5 p6 r# |+ D2 M: g int k=f;& d ?. [; @* P& a; F
if((k==0)||(*(str+i)!=*(str+k)))! r4 w; V* C* k
pre=k;$ I" ^6 _( \4 |* G; G
else
' y- O6 J' g! R4 C* } pre=pre[k];
! C8 m( w$ {0 p' T* O* c }
. e5 F V, Q8 Y delete []f;
! p H o' }) ]! m5 K}7 N% t* |/ A1 C& ~
int String::Match(int i,String& t)7 ~( W1 g7 `6 d. ^9 c
{
. }( m) c* Y6 `, m6 w int j=0;0 S# T0 h/ G2 H9 R" I' Y
int n=Length(),m=t.Length();
" s: L+ g' n& `+ _; H1 f t.ModifiedPrefix();5 j" G) e; S0 N# Y( L9 J& J
while((i<=n)&&(j<m))
: M5 Y2 r8 r7 m$ U. z if(str[i-1]==t.str[j])& |/ S' v. Z& s' t0 P
{5 T; N* K1 h7 N! M) J6 d& {1 h
i++;: G& G; m* U3 b: F& a
j++; e% W1 C( L2 A
}
9 g1 O9 h$ U* o9 f3 f; t7 }- r6 Q9 @ else
1 Z# W2 @, b& Z% l* K. v" k6 W if(j==0)
# Q# p7 f7 s% E/ ] i++;
) V, I: F: l+ L4 _! u* { else % D1 N3 q( p2 B) s$ r8 h
j=t.pre[j];
& C1 k! o9 `# S* l if(j<m); V! w# j) ~! V# K
return 0;/ x; d7 X& T& o b5 ^' L8 D4 \5 T
else
8 d8 L/ d/ ?' p- U return i-1;7 g6 o# v7 |' y# \+ m+ z
}/ S2 r# a( ]& l" K8 u, D
int main()
4 o# Q3 Y/ Y6 r( N$ e* `{
6 F4 M2 Q. o8 o) n! {1 W if(in.fail())
* J- s- C6 l4 J s$ B {
2 j5 u& j% Y' _% E& j cout<<"the input.txt is not exist!";
, H9 j3 L4 J3 D% T$ C( y9 o8 B exit(1);}
7 f1 H. e `) L3 d, X6 y& l# N0 z int i=1;
" l/ [* U0 l+ _+ m0 j7 l: P4 c; `: f String s,t;
6 U( [! ?! L; y3 J5 D/ F s.ReadString();' Q8 Y2 A# W' z/ v$ w, ]
while(t.Rs()+1)* S# l r( e9 V' d9 t
{6 u3 [' c$ g$ d
i=s.Match(i,t);# h. f' h7 c& p
if(!i)
/ `8 W7 C7 a" ]% e$ t( D8 D P2 D {) N2 t4 x2 |' r# @! j
out<<"No"<<endl;
. i0 }& [2 v" ^8 h+ p ^% |4 F break;
+ W( r" S5 o; A7 j- f: y. O }$ Y+ p7 Z2 d& ^
}
. k4 q# I4 u! }1 M. |& i( ^6 z if(i)
5 ~8 _$ W. a6 K3 k. ^4 m; e/ o# C; ?9 u# | out<<"Yes"<<endl;5 {1 P% z' [# }9 g0 ~% O2 j# U* o
return 0;% s, L3 Q3 H6 v4 G+ ^) A6 a
} |
zan
|