- 在线时间
- 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>
$ s. t" P% a$ v& E! u< >[[/hide]</P>#include <iostream># K( C! t1 w% _- I! Y. C
#include <fstream>
/ E) B' U% v9 y8 V* s. o- Fusing namespace std;
9 i' Q0 \* `6 C. ]ifstream in("input.txt");0 x: `" i9 { a% p9 f
ofstream out("output.txt");
3 m1 B6 ?6 P- \& S& ?class String
- H$ Q ]- d# Z- |{
/ T6 H! ^) [% q% a0 w$ o" A/ E3 i Y9 m public:* c* f$ M8 d7 I+ ?( `) T( @( y/ o4 u
String(char *s="");
# o$ N* o$ {: F! T A' Y* h* y/ g String(const String& s);
. i3 C$ B& b9 g5 ?( e1 s ~String();2 Y" b$ j0 P5 w( ]- _- u8 v- F- s
int Length() const;
" c. X4 p% o! H/ q/ ~ int ReadString();
) U' M9 T; x' ?. e* S2 t* Z( w int Rs();
4 B. G8 L, l8 r4 e5 h void Prefix();" K5 z. r& Y3 j, @& m& h# {
void ModifiedPrefix();2 H' x3 d1 B1 b
int Match(int i,String& t);/ C5 h6 Y7 s# i8 z& J
private:4 {8 v0 \ ?! M0 @$ j7 w
char *str;
D# m1 O( u! a int *pre;
. o5 H7 t% X0 r% P* c7 v int size;6 h( j3 w, @6 N W
};5 q: K( k& {0 a( G% U$ J1 ^
String::String(char *s)2 `2 ~: Q" U/ I: K8 a2 m+ s
{& Z0 a0 E0 k. A g2 D5 k1 ~& E
size=strlen(s)+1;
" n# W A) m3 ]1 f8 e; G/ S& \5 `; } str=new char[size];' r! y) R- ?3 Q* m, h' `; R8 n
if(str==0)$ n: c# q7 e6 f/ k3 y/ @& y
throw "error";
+ L- M0 }9 l! E, e8 j1 ]) q8 d' f strcpy(str,s);
" y8 K, ^6 A; Z pre=new int[size];1 U, [# Q( U, ~- K, o0 D
if(pre==0)
+ x* m" }% _! t8 T( h3 ^& s throw "error";
8 Q3 ~ O5 Y8 s4 i: L}
; T; T* f( X2 |4 a4 G t% tString::String(const String& s)
" F r, ?% F! D( ] @0 _9 \# K{) H2 H# q! W* _7 S( b6 S3 B: v
size=s.size;
4 y7 Q% Q* t; l7 B str=new char [size];
9 { K+ b9 ?- B! b N if(str==0)
! G6 A( V6 W4 M! h" z. p throw "error";' i0 Q& b$ V# v) C9 B% `! t
strcpy(str,s.str);4 L/ ^' m3 j! }' P& ]5 R
pre=new int [size];
9 W& |' Y7 K3 k5 [ if(pre==0)
m6 A& r8 s* T; C1 _ throw "error";2 e; @, k+ Y) r
}
a& \. B& d- S8 F7 o# NString::~String()
3 W: K; Q8 M1 N3 A7 z& n- G{
: F o' D+ F2 y6 ]3 e delete [] str;. c2 f1 s) z/ Z, h4 i- _2 R
delete [] pre;
+ G x I0 k2 B& C" F' O3 s# }}
3 F' e& q, H$ a/ X- B8 xint String: ength() const( m! p: p6 u8 Q5 ]0 \& [ b/ G
{8 F+ D5 f6 l3 |4 d
return size-1;
7 {( C6 n- f6 @}
6 t0 Q; G5 x0 m1 n8 G) {1 gint String::ReadString()' H' ^( d: @2 Q/ Q+ q; X
{
8 U$ D$ _" M; K7 f& L char tmp[256];2 `' I9 E" V, `; `
if(in>>tmp)" Z$ P' o. Z; J; ~' T3 A1 t
{0 ^3 i2 H1 o* V8 o/ V; n
delete [] str;
) T$ ]2 L# a) N% ~6 G4 x size=strlen(tmp)+1;2 B p5 P d/ Y5 }0 X
str=new char [size];
* ?- A7 _5 |) \8 \* M* v, f+ b* d strcpy(str,tmp);7 i3 d6 C1 m8 B, M" X0 z
return size-1;5 n \. u5 x% s6 o1 P
}
8 W/ \% p6 W& ~( { else) Y2 q4 _' m2 L( b6 m
return -1;
6 z5 ?$ S6 n9 Y5 e6 f. U" ~* b f}
' \+ h% k: t8 {: o/ ]int String::Rs()
: B5 B/ x) [/ B3 P% N) C3 G{
7 H. J" q' ~* ?1 r! }( C8 \ char tmp[256],c;
# a" e. }7 ^" |: T, M/ Q( N int i=0;
x: R: V; Z2 Y1 }" h6 W while(in>>c)
0 z& i: @' j3 {' k: J {1 k+ \* W! @; d& ^+ x8 {+ S% v
if(c!='*')7 z: l& c; w; n( d+ z0 `; P
tmp[i++]=c;6 m; g0 _5 a) h5 p8 `# C8 b% }
else if(c=='*'&&i>0)) m$ h/ Y9 d/ s* D/ T: f
break;
, S! u! n. M% E! e! O1 ? }, [8 w# f* b, o; J: F
if(i>0)
0 u0 a N2 m3 s: Q8 V0 y8 | {+ r2 w* F2 h, l" U% c \7 ]0 L
delete [] str;
5 M+ l, o j: b% J# o5 ^ size=i+1;
$ a( {" C) z n' L: E, P str=new char[size];
! G, I/ i! I5 U a- v7 y7 d if(str==0)
5 J1 U* o0 ~$ b! o5 Q/ { throw "error";0 e$ _' c+ \9 [
for(i=0;i<size-1;i++)5 y! n8 M' r: Q* h
str=tmp; * E+ [# r ~2 f8 [- `! X
return size-1;5 {' ?( Y8 |% I1 }! b5 x* H
}4 |& s% y( o0 W' G0 L
else \2 i) h( M% K ~ P
return -1;
/ V* y6 c8 b! O7 T5 ]9 t}
l8 u$ Z4 z5 k/ _void String: refix()
$ J- m4 G4 h# J0 C* h8 {) q{
6 G$ {3 b) i) G/ S* W, q5 I* H+ @ int m=Length();
+ X; p0 e" k% R1 n& K# J delete [] pre;
. \$ l- Q6 v6 L* o; Y% | t# h pre=new int [m+1];6 u- q2 s' H9 K& k! u9 L$ N
pre[1]=0;8 ^. X. G1 r1 [$ a5 ~
int k=0;. s0 r8 T" n/ }8 \( c0 g* G
for(int i=2;i<=m;i++)2 p$ A; D( F2 p8 c) b1 s# w5 W6 Y
{2 U. P# Y0 A- W- j4 l, \
while((*(str+i-1)!=*(str+k))&&(k>0))
, o/ }( h/ ]' ~, Q/ c" M$ o, E k=pre[k];- [# a @2 A }) P0 q, B
if(*(str+i-1)==*(str+k))
: F; {* p; p f pre=++k;
- o q7 O' E5 M. q& _ else6 ?6 Q# {2 l( g$ O
pre=0;4 b0 A" B# }. s
}
+ s. L! d8 [' ~% d* i2 U: i}/ O) N8 f1 ?! U0 o0 t
void String::ModifiedPrefix()% W6 F- x3 h+ V* Y/ O7 o
{
1 I' H+ O2 Q; w* a( V7 n% S! W9 S int *f;
E6 M8 b( h, f0 ^3 E9 H" V int m=Length();
# t# N; b, p b+ O f=new int[m+1];
* B6 Y/ t, C. e# d; h) Y' e4 x Prefix();
( X! a! y5 x0 R for(int i=1;i<=m;i++)$ n3 d8 L9 Z% E5 R
{. T# y; o" J& c+ |6 U+ O
f=pre;# q: A3 E/ `/ D/ k) V
}
- L! `8 T4 |3 O& `8 _2 C for(i=1;i<m;i++)
' N) S- P6 a6 Q4 l$ a( V' e {
, \" W9 Q2 | N int k=f;
- C1 X7 V6 j. \6 x if((k==0)||(*(str+i)!=*(str+k)))
& x& p! ~% U! Q9 T3 N pre=k;3 I- i# r- N9 }1 y# J5 b! _
else 9 I7 y- d9 s2 N. n
pre=pre[k];
" H1 F4 P' a$ V }
2 b. m3 E+ X, G7 v7 _/ G5 s' N delete []f;0 Z0 C% N, U; l- W
}8 }2 W! |- H$ s/ y" P
int String::Match(int i,String& t)* A4 ~5 ?: B6 j$ @" U* L
{. M7 q! t8 s8 _9 u i
int j=0;/ r3 s, N* _ x( ]- d3 ]) D
int n=Length(),m=t.Length();8 i+ \1 s9 u& S" @ N. C# x% z
t.ModifiedPrefix();0 n2 a! C w! f
while((i<=n)&&(j<m))
+ ?& K0 e+ S/ H, P G2 J; a/ y1 U. K if(str[i-1]==t.str[j])* E) x" B8 a& O) t' y% `6 S$ z( o
{- I) X! Q3 I0 R1 O4 r- N4 W. P
i++;
' I' `" F$ w9 p& |3 H j++;$ ]$ a8 U1 Z; L- `/ n2 F
}3 y0 k% Z! A; G. ^
else # J2 a4 v/ l1 T9 U* i
if(j==0)( [2 \4 G G* j- y
i++;
" K' K2 p+ {' }1 |! }" Y2 C else
2 W) K* F$ z/ L4 T1 P j=t.pre[j];
+ D5 {- w( R# M# g if(j<m)0 b' b' a6 ~& ^0 j. N8 F
return 0;
# e8 J0 v% B; x/ _- Y else ) r6 i, X$ a/ m9 W' h% Q
return i-1;
0 W8 n8 H, Y* P5 @4 S U}
; a5 }5 y1 @' {+ v+ m+ d; `int main()
5 e+ X8 R) @ g{& F5 a( g2 y& G2 G4 d& F
if(in.fail())
% z7 I, A9 S1 \3 [ {* l" \# g7 D @' I9 U* ]- g
cout<<"the input.txt is not exist!";) W) _0 X+ V0 W& L1 V' J( i
exit(1);} ~ m2 I4 a# A& e& D2 u! S
int i=1;" p- Z; a' V3 v0 z) x; t9 x- }. }
String s,t;- _7 i1 d5 @, {( U8 Y* z. j2 A
s.ReadString();
& m1 ~2 w; v6 H9 D: M while(t.Rs()+1)& ?9 d" Q1 j6 I
{4 M7 W) W- T, `2 [: y2 y
i=s.Match(i,t);8 w# _* y6 o# k$ b+ n/ v% Y
if(!i)
& Y5 H, `, l% w2 V8 C6 S% t1 s {0 p. ^, M4 }0 z
out<<"No"<<endl;
3 b1 b, I% ^/ K/ y5 [" y6 K3 n0 m1 R break;+ ?( W o* e3 k. S% z5 e% [
}
7 @* u, T* f4 X9 F) [ }
0 @3 A9 J8 q) O& \. w) V if(i)/ m4 m7 Y) t& A1 C
out<<"Yes"<<endl;
, h: N6 V# C$ f7 j return 0;
! U( q- a3 g9 J% a5 |: K2 a) M/ ~} |
zan
|