📄 usaco 2_3_1 longest prefix 题解_leokan的blog.mht
字号:
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.3.1 Longest Prefix =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C229=C8=D5 =D0=C7=C6=DA=B6=FE =
22:53</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.3.1 Longest Prefix</H2>
<DIV class=3Dt_msgfont>
<P>Longest Prefix<BR>IOI'96 <BR>The structure of some biological =
objects=20
is represented by the sequence of their constituents denoted by =
uppercase=20
letters. Biologists are interested in decomposing a long sequence =
into=20
shorter ones called primitives. <BR><BR>We say that a sequence S =
can be=20
composed from a given set of primitives P if there is a some =
sequence of=20
(possibly repeated) primitives from the set whose concatenation =
equals S.=20
Not necessarily all primitives need be present. For instance the =
sequence=20
ABABACABAABcan be composed from the set of primitives =
<BR><BR> =20
{A, AB, BA, CA, BBC}<BR><BR>The first K characters of S are the =
prefix of=20
S with length K. Write a program which accepts as input a set of=20
primitives and a sequence of constituents and then computes the =
length of=20
the longest prefix that can be composed from primitives. =
<BR><BR>PROGRAM=20
NAME: prefix<BR>INPUT FORMAT<BR>First, the input file contains the =
<SPAN=20
class=3Dt_tag href=3D"tag.php?name=3Dlis">lis</SPAN>t (length =
1..200) of=20
primitives (length 1..10) expressed as a series of space-separated =
strings=20
of upper-case characters on one or more lines. The <SPAN =
class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>t of primitives is =
terminated by a line=20
that contains nothing more than a period (`.'). No primitive =
appears twice=20
in the <SPAN class=3Dt_tag =
href=3D"tag.php?name=3Dlis">lis</SPAN>t. Then, the=20
input file contains a sequence S (length 1..200,000) expressed as =
one or=20
more lines, none of which exceed 76 letters in length. The =
"newlines" are=20
not part of the string S. <BR>SAMPLE INPUT (file prefix.in) <BR>A =
AB BA CA=20
BBC<BR>.<BR>ABABACABAABC<BR><BR>OUTPUT FORMAT<BR>A single line =
containing=20
an integer that is the length of the longest prefix that can be =
composed=20
from the set P. <BR>SAMPLE OUTPUT (file=20
prefix.out)<BR>11<BR><BR><BR><BR>Longest=20
Prefix<BR><BR>=D7=EE=B3=A4=C7=B0=D7=BA<BR>IOI'96<BR><BR>=D2=EB by =
Felicia=20
=
Crazy<BR><BR>=D4=DA=C9=FA=CE=EF=D1=A7=D6=D0=A3=AC=D2=BB=D0=A9=C9=FA=CE=EF=
=B5=C4=BD=E1=B9=B9=CA=C7=D3=C3=B0=FC=BA=AC=C6=E4=D2=AA=CB=D8=B5=C4=B4=F3=D0=
=B4=D7=D6=C4=B8=D0=F2=C1=D0=C0=B4=B1=ED=CA=BE=B5=C4=A1=A3=C9=FA=CE=EF=D1=A7=
=BC=D2=B6=D4=D3=DA=B0=D1=B3=A4=B5=C4=D0=F2=C1=D0=B7=D6=BD=E2=B3=C9=BD=CF=B6=
=CC=B5=C4=A3=A8=B3=C6=D6=AE=CE=AA=D4=AA=CB=D8=B5=C4=A3=A9=D0=F2=C1=D0=BA=DC=
=B8=D0=D0=CB=C8=A4=A1=A3=20
<BR><BR>=C8=E7=B9=FB=D2=BB=B8=F6=BC=AF=BA=CF P =
=D6=D0=B5=C4=D4=AA=CB=D8=BF=C9=D2=D4=CD=A8=B9=FD=B4=AE=C1=AA=A3=A8=D4=CA=D0=
=ED=D6=D8=B8=B4=A3=BB=B4=AE=C1=AA=A3=AC=CF=E0=B5=B1=D3=DA Pascal =
=D6=D0=B5=C4 =A1=B0+=A1=B1 =
=D4=CB=CB=E3=B7=FB=A3=A9=D7=E9=B3=C9=D2=BB=B8=F6=D0=F2=C1=D0 S=20
=A3=AC=C4=C7=C3=B4=CE=D2=C3=C7=C8=CF=CE=AA=D0=F2=C1=D0 S =
=BF=C9=D2=D4=B7=D6=BD=E2=CE=AA P =
=D6=D0=B5=C4=D4=AA=CB=D8=A1=A3=B2=A2=B2=BB=CA=C7=CB=F9=D3=D0=B5=C4=D4=AA=CB=
=D8=B6=BC=B1=D8=D0=EB=B3=F6=CF=D6=A1=A3=BE=D9=B8=F6=C0=FD=D7=D3=A3=AC=D0=F2=
=C1=D0 ABABACABAAB =
=BF=C9=D2=D4=B7=D6=BD=E2=CE=AA=CF=C2=C3=E6=BC=AF=BA=CF=D6=D0=B5=C4=D4=AA=CB=
=D8=A3=BA=20
<BR><BR> {A, AB, BA, CA, BBC}<BR><BR>=D0=F2=C1=D0 S =
=B5=C4=C7=B0=C3=E6 K =B8=F6=D7=D6=B7=FB=B3=C6=D7=F7 S =
=D6=D0=B3=A4=B6=C8=CE=AA K=20
=
=B5=C4=C7=B0=D7=BA=A1=A3=C9=E8=BC=C6=D2=BB=B8=F6=B3=CC=D0=F2=A3=AC=CA=E4=C8=
=EB=D2=BB=B8=F6=D4=AA=CB=D8=BC=AF=BA=CF=D2=D4=BC=B0=D2=BB=B8=F6=B4=F3=D0=B4=
=D7=D6=C4=B8=D0=F2=C1=D0=A3=AC=BC=C6=CB=E3=D5=E2=B8=F6=D0=F2=C1=D0=D7=EE=B3=
=A4=B5=C4=C7=B0=D7=BA=B5=C4=B3=A4=B6=C8=A1=A3 <BR><BR>PROGRAM NAME:=20
prefix<BR>INPUT FORMAT<BR>=CA=E4=C8=EB<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CA%FD%BE%DD">=CA=FD=BE=DD</SPAN>=B5=C4=BF=AA=CD=B7=
=B0=FC=C0=A8 1..200 =B8=F6=D4=AA=CB=D8=A3=A8=B3=A4=B6=C8=CE=AA 1..10=20
=
=A3=A9=D7=E9=B3=C9=B5=C4=BC=AF=BA=CF=A3=AC=D3=C3=C1=AC=D0=F8=B5=C4=D2=D4=BF=
=D5=B8=F1=B7=D6=BF=AA=B5=C4=D7=D6=B7=FB=B4=AE=B1=ED=CA=BE=A1=A3=D7=D6=C4=B8=
=C8=AB=B2=BF=CA=C7=B4=F3=D0=B4=A3=AC<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CA%FD%BE%DD">=CA=FD=BE=DD</SPAN>=BF=C9=C4=DC=B2=BB=
=D6=B9=D2=BB=D0=D0=A1=A3=D4=AA=CB=D8=BC=AF=BA=CF=BD=E1=CA=F8=B5=C4=B1=EA=D6=
=BE=CA=C7=D2=BB=B8=F6=D6=BB=B0=FC=BA=AC=D2=BB=B8=F6 =A1=B0.=A1=B1=20
=
=B5=C4=D0=D0=A1=A3=BC=AF=BA=CF=D6=D0=B5=C4=D4=AA=CB=D8=C3=BB=D3=D0=D6=D8=B8=
=B4=A1=A3=BD=D3=D7=C5=CA=C7=B4=F3=D0=B4=D7=D6=C4=B8=D0=F2=C1=D0 S =
=A3=AC=B3=A4=B6=C8=CE=AA 1..200,000 =
=A3=AC=D3=C3=D2=BB=D0=D0=BB=F2=D5=DF=B6=E0=D0=D0=B5=C4=D7=D6=B7=FB=B4=AE=C0=
=B4=B1=ED=CA=BE=A3=AC=C3=BF=D0=D0=B2=BB=B3=AC=B9=FD 76=20
=
=B8=F6=D7=D6=B7=FB=A1=A3=BB=BB=D0=D0=B7=FB=B2=A2=B2=BB=CA=C7=D0=F2=C1=D0 =
S =B5=C4=D2=BB=B2=BF=B7=D6=A1=A3<BR><BR>SAMPLE INPUT (file prefix.in) =
<BR>A AB BA CA=20
BBC<BR><BR>ABABACABAABC<BR><BR>OUTPUT =
FORMAT<BR>=D6=BB=D3=D0=D2=BB=D0=D0=A3=AC=CA=E4=B3=F6=D2=BB=B8=F6=D5=FB=CA=
=FD=A3=AC=B1=ED=CA=BE S =C4=DC=B9=BB=B7=D6=BD=E2=B3=C9 P=20
=
=D6=D0=D4=AA=CB=D8=B5=C4=D7=EE=B3=A4=C7=B0=D7=BA=B5=C4=B3=A4=B6=C8=A1=A3<=
BR><BR>SAMPLE OUTPUT (file prefix.out)<BR>11</P>
<HR>
<P></P></DIV>
<P><STRONG>USACO 2.3.1 Longest Prefix</STRONG></P>
=
<P><STRONG>=CE=CA=CC=E2=D6=D8=CA=F6:<BR>P=CA=C7=D2=BB=B8=F6=B0=FC=BA=AC=C8=
=F4=B8=C9=D7=D6=B7=FB=B4=AE=BC=AF=BA=CF,=C0=FD=C8=E7{A,BA,AB,...},S=CA=C7=
=D2=BB=B8=F6=D3=C9=B4=F3=D0=B4=D7=D6=C4=B8=D7=E9=B3=C9=B5=C4=D7=D6=B7=FB=B4=
=AE,=C8=E7=B9=FB=D2=BB=B8=F6=D7=D6=B7=FB=B4=AES=D6=D0=B5=C4=D2=BB=B8=F6=D7=
=D3=B4=AEs,=CA=B9=B5=C3s=D6=D0=CB=F9=D3=D0=D4=AA=CB=D8=BF=C9=D2=D4=D3=C9=BC=
=AF=BA=CFP=D6=D0=B5=C4=D4=AA=CB=D8=B9=B9=B3=C9,=D4=F2=B3=C6=D5=E2=D1=F9=B5=
=C4=D7=D6=B4=AE=CE=AA=BF=C9=D0=D0=B4=AE,=CF=D6=B8=F8=B3=F6=D2=BB=B8=F6=D7=
=D6=B7=FB=B4=AE(=B3=A4=B6=C8<=3D200000)=BA=CD=BC=AF=BA=CFP(=D4=AA=CB=D8=
=B8=F6=CA=FD<=3D200),=C7=F3=D7=EE=B3=A4=B5=C4=BF=C9=D0=D0=B4=AE=B5=C4=B3=
=A4=B6=C8.</STRONG></P>
=
<P><STRONG>=CE=CA=CC=E2=B7=D6=CE=F6:<BR>=D3=C3=B6=AF=CC=AC=B9=E6=BB=AE=D7=
=F6=A1=A3=BC=C7f(x)=CA=C7=D3=C9=D7=D6=B7=FB=B4=AE=D6=D0=B5=DAx=B8=F6=D7=D6=
=C4=B8=BF=AA=CA=BC=D2=BB=D6=B1=B5=BDS=C4=A9=CE=B2=B5=C4=D7=D3=B4=AE=D6=D0=
=D7=EE=B3=A4=B5=C4=BF=C9=D0=D0=B4=AE=B5=C4=B3=A4=B6=C8.=D3=C9=BA=F3=CD=F9=
=C7=B0=CD=C6,=C8=E7=B9=FB=BC=AF=BA=CFP=D6=D0=B5=C4=C4=B3=B8=F6=D4=AA=CB=D8=
a,=CB=FC=B5=C4=B3=A4=B6=C8=CE=AALa,=CB=FC=C8=AB=B5=C8=D3=DAS=B5=C4=D7=D3=B4=
=AEs(x=B5=BDx+La-1),=D4=F2f(x)=3DLa+f(x+La-1),=C8=E7=B9=FBf(x+La-1)=CE=AA=
0=BE=CD=CB=B5=C3=F7=C1=AC=BD=D3=B2=BB=C9=CF,=B4=CB=CA=B1=B8=C3=B3=A4=B6=C8=
=CE=AALa.=CE=AA=C1=CB=C4=DC=C8=A1=B5=BD=D7=EE=B4=F3=D6=B5,=C3=B6=BE=D9=C3=
=BF=D2=BB=B8=F6=BC=AF=BA=CF=D6=D0=B5=C4=D4=AA=CB=D8(=C4=DC=D3=EB=D7=D6=B4=
=AEs(x+Ly-1)=C6=A5=C5=E4=B5=C4=D4=AA=CB=D8),=B5=C3=B5=BD=D2=BB=B8=F6=BF=C9=
=D0=D0=B4=AE=B5=C4=B3=A4=B6=C8La+f(k),=C8=AB=B2=BF=C3=B6=BE=D9=CD=EA=BA=F3=
=C8=A1=D2=BB=B8=F6=D7=EE=B4=F3=D6=B5=D7=F7=CE=AAf(x)=B5=C4=D6=B5.=D5=E2=D1=
=F9=D3=C3=D7=EE=CE=B2=CD=F9=CD=B7=CD=C6,=CD=C6=CD=EA=BA=F3=B5=C4f(1)=D4=F2=
=CE=AA=CB=F9=C7=F3=B4=F0=B0=B8.</STRONG></P>
<P><STRONG>{<BR>TASK:prefix<BR>LANG:PASCAL<BR>}<BR>program=20
prefix;<BR>var<BR> dict:array[1..200] of=20
string;<BR> dictp:integer;<BR> =
len:longint;<BR> =
s:ansistring;<BR> =20
f:array[1..200001] of longint;<BR> =
is:array[1..200001]=20
of boolean;<BR>procedure init;<BR>var<BR> =20
st:string;<BR> ch:char;<BR> =20
i:integer;<BR> =20
noon:boolean;<BR>begin<BR> =20
assign(input,'prefix.in');reset(input);<BR> =20
dictp:=3D0;<BR> st:=3D'';<BR> =
while true=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
while not eoln=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
read(ch);<BR> =
=20
if ch=3D'.'=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
if st<>''=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =
=20
=
inc(dictp);<BR> &nbs=
p;  =
; =
=20
=
dict[dictp]:=3Dst;<BR> &nb=
sp; &nbs=
p;  =
; =20
=
st:=3D'';<BR> =
&=
nbsp; =20
=
end;<BR>  =
; =
=20
=
break;<BR> &nb=
sp; &nbs=
p;=20
=
end;<BR>  =
; =20
if ch in ['A'..'Z'] then=20
=
st:=3Dst+ch<BR> &nbs=
p; =20
else if st<>''=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(dictp);<BR> &nbs=
p;  =
; =20
=
dict[dictp]:=3Dst;<BR> &nb=
sp; &nbs=
p; =20
=
st:=3D'';<BR> =
&=
nbsp;=20
=
end;<BR>  =
; =20
=
end;<BR>  =
;=20
if st<>''=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
inc(dictp);<BR> &nbs=
p; =20
=
dict[dictp]:=3Dst;<BR> &nb=
sp; =20
=
st:=3D'';<BR> =
=20
=
end;<BR>  =
;=20
if ch=3D'.'=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
readln;<BR> &n=
bsp; =20
=
break;<BR> &nb=
sp; =20
=
end;<BR>  =
;=20
readln;<BR> =20
end;<BR> noon:=3Dtrue;<BR> =
while noon=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
noon:=3Dfalse;<BR> &=
nbsp; =20
for i:=3D1 to dictp-1=20
=
do<BR> &=
nbsp; =20
if length(dict[i])>length(dict[i+1])=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
st:=3Ddict[i];<BR> &=
nbsp; &n=
bsp; =20
=
dict[i]:=3Ddict[i+1];<BR> =
&=
nbsp; =20
=
dict[i+1]:=3Dst;<BR>  =
; =
=20
=
noon:=3Dtrue;<BR> &n=
bsp; =20
end;<BR> =20
end;<BR> len:=3D0;<BR> =20
st:=3D'';<BR> s:=3D'';<BR> =
while not eof=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
readln(st);<BR> &nbs=
p; =20
s:=3Ds+st;<BR> =20
end;<BR> len:=3Dlength(s);<BR> =
close(input);<BR>end;<BR>function=20
max(x,y:longint):longint;<BR>begin<BR> if x>y =
then=20
exit(x)<BR> else exit(y);<BR>end;<BR>function=20
min(x,y:longint):longint;<BR>begin<BR> if x>y =
then=20
exit(y)<BR> else exit(x);<BR>end;<BR>function=20
check(st:string;x:longint ):boolean;<BR>var<BR> =20
i:integer;<BR>begin<BR> if length(st)+x-1>len =
then=20
exit(false);<BR> for i:=3D1 to length(st)=20
do<BR> if =
st[i]<>s[x+i-1]=20
then exit(false);<BR> =
exit(true);<BR>end;<BR>procedure=20
dp;<BR>var<BR> =
i,j,maxlen:longint;<BR> =20
t:boolean;<BR>begin<BR> =20
assign(output,'prefix.out');rewrite(output);<BR> =
fillchar(is,sizeof(is),0);<BR> =20
fillchar(f,sizeof(f),false);<BR> for i:=3Dlen =
downto 1=20
do<BR> for j:=3D1 to =
dictp=20
=
do<BR> =
if check(dict[j],i)=20
=
then<BR>  =
; =20
=
f[i]:=3Dmax(f[i],length(dict[j])+f[i+length(dict[j])]);<BR> &n=
bsp;=20
writeln(f[1]);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> dp;<BR>end.<BR></STRONG></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>usaco=B5=C4=B7=D6=CE=F6,=C4=D1=B5=C3=D3=D0pascal=B5=C4=B0=A1</=
STRONG></P>
<P><STRONG>The basic tool to use here is dynamic programming. For =
each=20
prefix of the sequence, you know that it is expressible in terms =
of the=20
primitives if and only if you can find some shorter expressible =
prefix=20
such that the sequence between the two prefixes is a primitive. =
Thus, you=20
can check each primitive and see if it matches the end of a prefix =
and=20
whether the prefix before that primitive (the pre-prefix, if you =
would) is=20
expressible. </STRONG></P>
<P><STRONG>This can be turned-around to get something that is =
simpler to=20
code. For each prefix that is expressible, determine which =
primitives=20
match the sequence beginning at that location, and mark the prefix =
plus=20
the primitive as expressible, if it does. </STRONG></P>
<P><STRONG>In the worst case, you have to check each prefix =
starting at=20
each location. There are at most 200 prefixes of length 10 to =
check at=20
each of 200,000 locations, for a total of 400,000,000 operations. =
This is=20
a little higher than the standard number you would expect to be =
able to do=20
in 5 seconds, but it is a very small operation (two array look-ups =
and a=20
character comparison), and an over-estimate on how bad it can =
actually=20
get. </STRONG></P><PRE><STRONG>#include <stdio.h>
/* maximum number of primitives */
#define MAXP 200
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -