- 在线时间
- 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>
9 V! U [" i/ J7 v1 L! Q' z0 y' u< >[[/hide]</P>#include <iostream>
A7 o0 z; t! D7 b+ q#include <fstream>
% c8 k m. h( U: iusing namespace std;
" w, X0 n8 g5 F2 |: d9 V/ Gifstream in("input.txt");3 N/ l+ q8 _! j; @8 s* w
ofstream out("output.txt");3 T' q& V6 L5 N4 V( x. j% R8 l
class String4 i: a; A. ~( T) \3 x
{. o% `4 F$ s2 y6 n% z
public:
- y7 |5 @$ d$ [6 s P% R* b" ? String(char *s="");- I! w+ |+ h" @# M3 d- l5 E0 I6 T
String(const String& s);
2 }" u+ [$ |. Y+ Y% o& w4 X X ~String();
1 c* N( k7 V- v m" I" Q% v% l int Length() const;
: \. F' O" g; h, o: j int ReadString();
8 H& b4 \- k$ R9 O: E+ I int Rs();( Y) q7 E1 q( @' q) N7 I+ b
void Prefix();
0 n" b, s- c5 U( C8 s5 E: @. f void ModifiedPrefix();
; h: Z9 w) z* M int Match(int i,String& t);* |! r9 c& n3 [1 _
private:
2 J" W2 k/ L5 M" H! F, K: x' x# E6 s char *str;2 U5 a/ E/ S* v0 A `- a7 Z- o+ H# r% o
int *pre;0 d8 ? L* h6 X/ I C5 O* c5 i
int size;
8 ^$ N `' Q2 \+ g. v};
' M1 S, Z2 K; r# g! r0 WString::String(char *s)- R+ r5 z# b! |8 T
{% p) P( O9 I9 u
size=strlen(s)+1;/ q9 z/ x9 z7 f. i, |# h9 x
str=new char[size];
9 u/ h, I0 {3 J) D* J& L' i- z; A if(str==0)1 s5 Q1 ?9 f5 ?8 O
throw "error";
" D- u' S% U0 j3 a4 z3 M4 N strcpy(str,s);2 B& U+ l G" |1 N
pre=new int[size];
( s9 P( J/ P* R* ~+ E0 ] if(pre==0)8 R2 [" M% L3 j' L! O
throw "error";; |( w: O( M7 l( z* t) ]
}$ k) j/ {" z6 O
String::String(const String& s)
$ G, N* @/ d3 N1 E{
% L. }1 [( y5 X' s Z3 [ size=s.size;
% N/ F$ P5 Q$ ]" e4 y str=new char [size];
% B q6 j& j; H" i* a' V3 ^ if(str==0)8 ?, a" J9 L$ q
throw "error";
6 Q; U4 f7 A9 h5 r" l strcpy(str,s.str);, R5 P& ~7 C' h' V) m, J
pre=new int [size];
/ t0 H2 O X4 w if(pre==0)8 {( D$ b$ P2 Z* [
throw "error"; r0 z& N5 N2 J+ a2 L- p- Z
}
) y1 }1 m$ B7 Q) bString::~String()2 z2 S: E+ G7 {- }
{# w2 Q9 h( t' d) I7 @1 `
delete [] str;
# |" \( x0 _ O8 D delete [] pre;
6 @1 R9 w9 v( U7 [1 y+ U, i}
4 ?' N" s+ I8 L0 w; Zint String: ength() const" q0 A M9 P# q# @0 e
{
8 q j$ l$ k3 x' m2 A& y0 ] return size-1;8 n( x, q+ A6 b+ k
}: B n& M; g0 j$ c2 M
int String::ReadString()$ A6 g; |( ~0 i' R
{$ ?0 n, b0 y9 P* Q
char tmp[256];
6 i9 |/ X- D9 b f& i if(in>>tmp)# u0 p! x4 Z! S7 u% q1 ?
{6 z( V. J$ v z9 y4 k
delete [] str;
/ V) j. Z# \% e" h; M/ r6 l K size=strlen(tmp)+1;, |$ d. b y3 W8 m
str=new char [size];
( m2 A# r: M E8 T K strcpy(str,tmp);9 t' g7 s! _1 e
return size-1;/ s1 w# n- [8 s% E8 o" y
}
) }' d; n( [& R- t else
( I6 ^9 n1 n! v" N return -1;* _2 N0 f& b/ r: z9 C0 a) l* S
}$ E* {/ x: ^6 a- W8 F
int String::Rs(): s% P7 W; W8 ?( R8 R' l1 C
{& Q8 A8 _6 g* G3 I: X4 \5 `7 @
char tmp[256],c;
) s3 r* S5 w* z7 c! u: d* A: Z int i=0;- }/ ` V$ p y4 Y7 p" d Y) g
while(in>>c)
) X4 {9 ]0 A \; t/ q% ], n {
' T+ j4 _ | t: `2 F) E if(c!='*')
1 B# ]$ g% O9 B0 H* G tmp[i++]=c;! @, n8 O; F6 b) z& K
else if(c=='*'&&i>0)
$ P4 q1 l) J( m! {4 ]9 g& E break;% J5 Z4 F! b" g/ \ Y# W
}
- z. c! M/ u3 q1 X5 Z if(i>0)( u [9 L# |* D
{
4 l$ D# `' c' V' |( ~. r5 z, j delete [] str;
! w) \. P6 u/ C9 L p size=i+1;
5 h1 {. L* N! ]% G2 e6 E4 X1 Z str=new char[size];
, F) T. y# `+ O5 n; @8 S if(str==0)1 V# |5 _0 a% f1 O0 V$ c
throw "error";
3 ^: D t1 c( j$ O2 m0 R8 m for(i=0;i<size-1;i++)
$ z i+ A" ]1 B. X5 _% M1 B* n str=tmp;
" x) n' ~/ t+ x% h7 N/ m+ C return size-1;0 o7 @; D# j, z5 @6 Z3 Q3 e
}1 b- V. k2 y* r6 w i, S
else. g2 T) j* b1 X
return -1;
) x6 D$ W" L5 T' r$ n8 p3 R}
8 u, }) Y0 z' G8 _! r! Evoid String: refix()8 m6 c: p7 K: O p+ k
{
6 f; ^4 H2 x' r7 f( H6 \ int m=Length();+ L' U' e* V! f4 F* o
delete [] pre;
7 {4 V6 x( K8 |% r f2 h7 {0 W pre=new int [m+1];
1 o' d! Y( |' v) q g pre[1]=0;0 i& `2 U0 O' p& L1 J4 T
int k=0;
- n1 Y) b- Y/ s2 @# v for(int i=2;i<=m;i++)
9 w" [. Q1 o) }, M4 C {0 N9 w# ?& w5 q2 @% K
while((*(str+i-1)!=*(str+k))&&(k>0)), r5 F0 W0 s- s3 n2 E% {0 W% X
k=pre[k];
8 C$ Z$ n$ o! U: {- U% R if(*(str+i-1)==*(str+k))
3 A5 T1 [" H8 `" W pre=++k;$ c* K) b+ K0 C1 i; O" D6 l
else
( @ P8 U4 ?% t3 L pre=0;
" V2 r, _2 [* _( s9 T$ q: [ }
$ _4 j7 v$ g8 `}6 @( |+ T% Z7 P& C% Y% q
void String::ModifiedPrefix()
: z3 p2 T- A1 {2 g; \% W- c{
1 X+ d! P, t8 `8 J) R1 x2 |# M" u int *f;& W( U% d/ h5 q9 }. J! Z4 B
int m=Length();
% S- |4 Q4 g( ~$ L: e& l% ` f=new int[m+1];
' \ v" l. c6 @ P3 g Prefix();. C/ |; [3 B; B6 B
for(int i=1;i<=m;i++)1 P6 Z, r, [( E7 R- h: l7 X- b
{
7 p0 M' Y7 V \ f=pre;4 }- _7 P" D* F) u3 l! i0 ]
}
, K: f; L8 K! u$ Q* X+ u for(i=1;i<m;i++)
$ o& m' G1 x+ g1 K {
; a: s. D8 M) M+ _" \+ A int k=f;
: r3 \* W5 H& B, N if((k==0)||(*(str+i)!=*(str+k)))8 ?& O. w7 [+ ]" x# x" ?
pre=k;
- W) \# Y: p; Q0 |& r4 m- P else ; l# b( o9 K- ?6 X1 Z5 l& G
pre=pre[k];: X8 s( M; I! x7 P' v' u" D+ B
}
6 z' b7 R& L9 c+ M% V delete []f;
# t# H3 o/ b: Y9 ~- h( v Y}
( o" P5 n' @" [" Y2 [" x* ^! Oint String::Match(int i,String& t)3 C% T4 m7 u& e4 ?, F% S2 E) k
{
* S7 C# X8 }) k% K# h; Y2 { int j=0;
, e: O+ O$ w$ F- [' S; |4 w& C int n=Length(),m=t.Length();1 [, A1 p0 ?, [9 G4 W" i
t.ModifiedPrefix();8 z4 W9 \' m. K8 V; W* o
while((i<=n)&&(j<m))% O5 `+ D0 _9 u# h, N7 Y
if(str[i-1]==t.str[j])/ t3 n2 Z6 p3 t
{
* F3 x5 l/ ]4 p5 ~" ~$ ]' A: @ i++;$ x! {- g0 H0 @5 K0 j
j++;
$ E' H0 h' Q1 m }
; d! {$ J. W$ l, r9 ~ else % {$ |' q2 z3 D! N- I2 U# W2 V
if(j==0)
/ n5 W& t2 r2 B8 } i++;
/ E( g6 r$ @9 \% s. p8 [" M else 7 H# S. r: k7 ^' a" b, q/ S
j=t.pre[j];
q; V4 ~4 y" \8 i% b4 ] if(j<m)
; z$ o+ N, I) E return 0;
2 X% n+ V- b# U+ k7 p# n5 D else 9 d& v6 y4 k' l' y
return i-1;) o9 D" ~ Y- W$ ~0 f
}
, [4 ^, ?- N& Y0 i# s i; K8 A0 O2 L" }int main()
3 ^& K f* X. C{! X4 N; {, V: x2 m4 a3 X2 l
if(in.fail())
- J( \3 x; R5 x {; B: R/ H+ `' \6 u) r3 n, W3 }3 S; `
cout<<"the input.txt is not exist!";# R( u' {3 `( m* I7 t6 N+ c
exit(1);}4 l# O, t1 o+ v5 {% g( ?
int i=1;5 U- n+ G D7 h% y
String s,t;
$ @, b1 u' _9 ?0 t5 X s.ReadString();
3 y5 G- M( Q, |, Y while(t.Rs()+1)4 @* W) J: j0 M
{% \& x6 [: d' r9 V* D
i=s.Match(i,t);! k, v* |, l# J Y/ `
if(!i)5 U- N0 k3 W0 j; I# @
{0 H0 _1 F4 |) s7 x: `0 ]
out<<"No"<<endl;/ _5 j3 M1 N+ ^0 P4 i
break;
# q! ] p: \+ |4 L/ k0 N7 w, k }
8 b% d/ G- y' X8 A3 t }$ r! M# R6 k! V9 ]# P& V( i
if(i)8 v9 o N+ k8 I9 u5 W! o2 ~
out<<"Yes"<<endl;9 j4 S( \1 h; z4 I: T' i
return 0;0 O& d* o4 T% U8 P |1 I( g
} |
zan
|