usaco 2_3_1 longest prefix 题解_leokan的blog.mht

美国USACO题库源程序

/* maximum length of a primitive */
#define MAXL 10

char prim[MAXP+1][MAXL+1]; /* primitives */
int nump;                  /* number of primitives */

int start[200001];         /* is this prefix of the sequence =
expressible? */
char data[200000];         /* the sequence */
int ndata;                 /* length of the sequence */

int main(int argc, char **argv)
 {
  FILE *fout, *fin;
  int best;
  int lv, lv2, lv3;

  if ((fin =3D fopen("prim.in", "r")) =3D=3D NULL)
   {
    perror ("fopen fin");
      exit(1);
   }
  if ((fout =3D fopen("prim.out", "w")) =3D=3D NULL)
   {
    perror ("fopen fout");
    exit(1);
   }

  /* read in primitives */
  while (1)
   {
    fscanf (fin, "%s", prim[nump]);
    if (prim[nump][0] !=3D '.') nump++;
    else break;
   }

  /* read in string, one line at a time */
  ndata =3D 0;
  while (fscanf (fin, "%s", data+ndata) =3D=3D 1)
    ndata +=3D strlen(data+ndata);

  start[0] =3D 1;
  best =3D 0;
  for (lv =3D 0; lv < ndata; lv++)
    if (start[lv])=20
     { /* for each expressible prefix */
      best =3D lv; /* we found a longer expressible prefix! */
      /* for each primitive, determine the the sequence starting at
         this location matches it */
      for (lv2 =3D 0; lv2 < nump; lv2++)
       {
        for (lv3 =3D 0; lv + lv3 < ndata &&  prim[lv2][lv3] =
&&
     prim[lv2][lv3] =3D=3D data[lv+lv3]; lv3++)
          ;
 if (!prim[lv2][lv3])   /* it matched! */
   start[lv + lv3] =3D 1; /* so the expanded prefix is also expressive =
*/
       }
     }=20

  /* see if the entire sequence is expressible */
  if (start[ndata]) best =3D ndata;=20

  fprintf (fout, "%i\n", best);
  return 0;
 }
</STRONG></PRE>
      <H3>Additional Analysis from Marian Dvorsky in Slovakia</H3>
      <P><STRONG>After the main idea is clear, we can think about an=20
      improvements. First of all we notice that a trick can reduce space =

      complexity from O(n) (where n is 200,000 - length of sequence) to =
O(maxl)=20
      (where maxl is 10, the length of the longest word in dictionary), =
but that=20
      requires an "opposite" method to the one Hal used in his program. =
For all=20
      prefixes of length n (n grows in increasing order), we check if =
they are=20
      expressible in terms of primitives. </STRONG></P>
      <P><STRONG>The second improvement is the check for whether the end =

      (suffix) of prefix is primitive. This can be also done in O(maxl) =
with a=20
      structure called a `trie'. We will have a tree in which every node =

      represents some word (or prefix of some word) in a dictionary and =
edges=20
      represent characters. The root of the tree represents an empty =
word.=20
      </STRONG></P>
      <P><STRONG>If we walk from root to some node `i' and write down =
characters=20
      on edges we've used, we get some word `v'. The node `i' then =
represents=20
      word `v'. Moreover if word `v' is in dictionary, we will remember =
it in=20
      that node (with some boolean variable). </STRONG></P>
      <P><STRONG>Finally, when we learn that the last maxl prefixes =
aren't=20
      expressible, then no more prefixes are, so we can exit =
immediately.=20
      </STRONG></P>
      <P><STRONG>In the worst case, we will, for every prefix (200,000), =
check a=20
      word of length maxl (10), for a total of 2,000,000 `operations'.=20
      </STRONG></P><PRE><STRONG>(* maximum length of primitive *)
const MAXL=3D20;

type pnode=3D^node;
     node=3Drecord
            next:array['A'..'Z'] of pnode;
            isthere:boolean;
          end;

var trie:pnode;     (* dictionary *)
    p:pointer;
    fin,fout:text;

(* read space separated word from file *)
function readword:string;
var s:string;
    ch:char;
begin
  read(fin,ch);
  while (not (ch in ['A'..'Z','.'])) do
    read(fin,ch);
  s:=3D'';
  while (ch in ['A'..'Z','.']) do
  begin
    s:=3Ds+ch;
    read(fin,ch);
  end;
  readword:=3Ds;
end;

(* read dictionary *)
procedure readdict;
var n,i,j,l:integer;
    nod:pnode;
    ch,ch2:char;
    s:string;
begin
  new(trie);
  for ch2:=3D'A' to 'Z' do
    trie^.next[ch2]:=3Dnil;
  trie^.isthere:=3Dfalse;
  s:=3Dreadword;
  while s&lt;&gt;'.' do
  begin
    nod:=3Dtrie;
    l:=3Dlength(s);
    (* save word in reverse order *)
    for j:=3Dl downto 1 do
    begin
      ch:=3Ds[j];
      if nod^.next[ch]=3Dnil then
      begin
        new(nod^.next[ch]);
        for ch2:=3D'A' to 'Z' do
          nod^.next[ch]^.next[ch2]:=3Dnil;
        nod^.next[ch]^.isthere:=3Dfalse;
  end;
      nod:=3Dnod^.next[ch];
    end;
    nod^.isthere:=3Dtrue;
    s:=3Dreadword;
  end;
end;

procedure compute;
var start:array[0..MAXL] of boolean; (* is this prefix (mod MAXL) =
expressible ? *)
    data:array[0..MAXL] of char;     (* the sequence (mod MAXL) *)
    i,k:integer;
    ch:char;
    nod:pnode;
    max,cnt:longint;
begin
  start[0]:=3Dtrue;
  read(fin,ch);
  data[0]:=3D#0; (* sentinel *)
  i:=3D1;
  max:=3D0; cnt:=3D1;
  while not eof(fin) do
  begin
    if not (ch in ['A'..'Z']) then
  begin
      read(fin,ch);
      continue;
  end;
    if i=3DMAXL then i:=3D0;  (* i:=3Di mod MAXL *)
    k:=3Di;
    data[i]:=3Dch;
    start[i]:=3Dfalse;
    nod:=3Dtrie;
    (* is there primitive at the and of current prefix ? *)
    while nod&lt;&gt;nil do
    begin
      nod:=3Dnod^.next[data[k]];
      dec(k); if k&lt;0 then k:=3DMAXL-1;
      if start[k] and (nod&lt;&gt;nil) and nod^.isthere then
      begin
        (* we've found a primitive at the end of prefix and the rest is
           expressible *)
    start[i]:=3Dtrue;
        max:=3Dcnt; break;
      end;
      if data[k]=3D#0 then break;
    end;
    read(fin,ch);

    (* if last MAXL prefixes are not expressible, no other prefix can
     be expressible *)
    if cnt&gt;max+MAXL then break;

    inc(i); inc(cnt);
  end;

  (* write answer *)
  assign(fout,'prefix.out');
  rewrite(fout);
  writeln(fout,max);
  close(fout);
end;

begin
  mark(p);
  assign(fin,'prefix.in');
  reset(fin);
  readdict;
  compute;
  close(fin);
  release(p);
end.</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
href=3D"http://hi.baidu.com/leokan/modify/blog/d47c5cdaead65bdfb6fd48bd">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/d47c5cdaead65bdfb6fd48bd.htm=
l#">=C9=BE=B3=FD</A>=20

<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3Dd47c5cdaead65bdfb6fd48bd=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
	<!--

function blogdel(str)
{
	var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
	pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
	=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
	pop.setContent("callBack",delCallback);
	pop.setContent("parameter",{fid:str,popup:pop});
	pop.build();
	pop.show();
	return false;
}

function delCallback(para)
{
	var o_pop=3Dpara["popup"];
	o_pop.config.contentType=3D1;
	o_pop.setContent("contentUrl","");
	o_pop.reBuild();
	G(para["fid"]).target=3Do_pop.iframeIdName;
	eval("document."+para["fid"]).submit();
}
	//-->
	</SCRIPT>
| <A =
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
 onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/d47c5cdaead65bdfb6fd48bd.htm=
l#send">=C6=C0=C2=DB</A>&nbsp;(0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 2.3.2 Cow Pedigrees =CC=E2=BD=E2', 'USACO 2.3.2 =
Cow Pedigrees =
=CC=E2=BD=E2','/leokan/blog/item/a8fca034599fd0b3d0a2d3bd.html'];
var post =3D [true,'USACO 2.2.3 Zero Sum =CC=E2=BD=E2','USACO 2.2.3 Zero =
Sum =CC=E2=BD=E2', '/leokan/blog/item/f9a73729047b82fa98250a2e.html'];
if(pre[0] || post[0]){
	document.write('<div =
style=3D"height:5px;line-height:5px;">&nbsp;</div><div id=3D"in_nav">');
	if(pre[0]){
		document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' +  pre[2] + '</a>&nbsp;&nbsp;&nbsp;&nbsp;');
	}
	if(post[0]){
		document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' +  post[2] + '</a>');
	}
	document.write('</div>');
}
/*]]>*/
</SCRIPT>
 </DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
	TEXT-DECORATION: none
}
</STYLE>

<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
    if(arg.length <=3D 1) return false;
    var hasMore =3D arg[0];
    var D=3Dfunction(A,B){A[A.length]=3DB;}
    if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);

    var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
    D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
    for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
        D(html, '<tr>');
        D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>&#8226;</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
        D(html, new Array(10).join('\u3000'));
        D(html, '</td>');
        if(arg[i + 1][0] !=3D "")
            D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>&#8226;</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
        else
            D(html, '<td>&nbsp;</td><td>&nbsp;</td>');
        D(html, '</tr>');
    }
    if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%202%2E3%2E1=
%20Longest%20Prefix%20%CC%E2%BD%E2&item=3Dd47c5cdaead65bdfb6fd48bd">=B8=FC=
=B6=E0&gt;&gt;</a></td></tr>');
    D(html, '</table></div><div class=3D"line">&nbsp;</div>');

    var div =3D document.getElementById('in_related_tmp');
    if(div){
        div.innerHTML =3D html.join('');
        while(div.firstChild){
            div.parentNode.insertBefore(div.firstChild, div);
        }
        div.parentNode.removeChild(div);
    }
}

if(RelatedDocData =3D=3D -1){	// not supported xhr
    var script =3D document.createElement('script');
    script.type =3D 'text/javascript';
    script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%202%2E3%2E1%20Longest%20Prefix%20%CC%E=
2%BD%E2&item=3Dd47c5cdaead65bdfb6fd48bd&t=3D' + new Date().getTime();
    document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
	GetAndEval =3D true;
}else{
	eval(RelatedDocData);
}

/*]]>*/
</SCRIPT>

<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>

	var g_spAnnony=3Dfalse;


var g_read=3D[
=09
["style007","61cb7374796c653030370f02","style007"],
=09
["saintqdd","a8b9cbaec5a3a1e1546f546f7e03","=CB=AE=C5=A3=A1=E1ToTo"],

{}
];
g_read.length=3Dg_read.length-1;

var _rh1=3D"";
var _rh2=3D"";

function wrreader(){
	_rh1 +=3D '<table width=3D"100%" ><tr>';
	_rh2+=3D'<tr>';
	if(g_spAnnony){
		_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
		_rh2+=3D'<td>&nbsp;</td>';
		if(g_read.length>0){
			_rh1+=3D'<td align=3D"left" width=3D"12%">';
		}else{
			_rh1+=3D'<td align=3D"left" width=3D"100%">';
		}
		_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
		_rh2+=3D'<td>&nbsp;</td>'
	}
	if(g_read.length=3D=3D0){
		if(!g_spAnnony){
			_rh1+=3D'<td align=3Dleft =
width=3D"100%">=D7=EE=BD=FC=BB=B9=C3=BB=D3=D0=B5=C7=C2=BC=D3=C3=BB=A7=BF=B4=
=B9=FD=D5=E2=C6=AA=CE=C4=D5=C2=A1=AD=A1=AD</td>';