ac1204.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1204;
const
  maxtrie=20000;
  maxtext=5000;
var
  trie:array[0..maxtrie]of record
         letter:char;attrib:byte;left,right:word;
         //Attrib: 4--noun,2--verb,1--auxiliary
       end;
  txt:array[1..maxtext+1]of char;
  sentn,wordn,sentv,wordv:array[1..maxtext]of word;
  n,i,p,l,j,tsent,tword:word;
  c,ch:char;
function min(a,b:word):word;
  begin
    if a<b then min:=a else min:=b;
  end;
begin
  repeat
    fillchar(trie,sizeof(trie),0);
    readln(n);l:=0;
    for i:=1 to n do begin
      read(ch,c);p:=0;
      while not eoln do
        if trie[p].left=0 then begin
          inc(l);trie[p].left:=l;p:=l;read(trie[p].letter);
        end
        else begin
          read(c);p:=trie[p].left;
          while (trie[p].letter<>c) and (trie[p].right>0) do p:=trie[p].right;
          if trie[p].letter<>c then begin
            inc(l);trie[p].right:=l;p:=l;trie[p].letter:=c;
          end;
        end;
      readln;
      case ch of
        'n':trie[p].attrib:=trie[p].attrib or 4;
        'v':trie[p].attrib:=trie[p].attrib or 2;
        'a':trie[p].attrib:=trie[p].attrib or 1;
      end;
    end;
    l:=0;
    repeat
      inc(l);read(txt[l]);
    until txt[l]='.';

    for i:=l-1 downto 1 do begin
      sentn[i]:=maxint;wordn[i]:=maxint;
      sentv[i]:=maxint;wordv[i]:=maxint;
      p:=0;j:=i;
      repeat
        p:=trie[p].left;
        while (trie[p].letter<>txt[j]) and (trie[p].right>0) do p:=trie[p].right;
        if trie[p].letter<>txt[j] then break;
        inc(j);
        //Noun
        if trie[p].attrib and 4>0 then
          if j=l then begin
            sentn[i]:=1;wordn[i]:=1;
          end
          else begin
            if (sentn[j]+1<sentv[j]) or (sentn[j]+1=sentv[j]) and (wordn[j]<wordv[j]) then begin
              tsent:=sentn[j]+1;tword:=wordn[j]+1;
            end
            else begin
              tsent:=sentv[j];tword:=wordv[j]+1;
            end;
            if tsent<sentn[i] then begin
              sentn[i]:=tsent;wordn[i]:=tword;
            end
            else if (tsent=sentn[i]) and (tword<wordn[i]) then
              wordn[i]:=tword;
          end;
        //Verb
        if trie[p].attrib and 2>0 then
          if j=l then begin
            sentv[i]:=1;wordv[i]:=1;
          end
          else begin
            if sentn[j]<sentv[i] then begin
              sentv[i]:=sentn[j];wordv[i]:=wordn[j]+1;
            end
            else if (sentn[j]=sentv[i]) and (wordn[j]+1<wordv[i]) then
              wordv[i]:=wordn[j]+1;
          end;
        //Auxiliary
        if (trie[p].attrib and 1>0) and (j<l) then begin
          if sentn[j]<sentn[i] then begin
            sentn[i]:=sentn[j];wordn[i]:=wordn[j]+1;
          end
          else if (sentn[j]=sentn[i]) and (wordn[j]+1<wordn[i]) then
            wordn[i]:=wordn[j]+1;
          if sentv[j]<sentv[i] then begin
            sentv[i]:=sentv[j];wordv[i]:=wordv[j]+1;
          end
          else if (sentv[j]=sentv[i]) and (wordv[j]+1<wordv[i]) then
            wordv[i]:=wordv[j]+1;
        end;
      until trie[p].left=0;
    end;
    writeln(sentn[1]);writeln(wordn[1]);
  until seekeof;
end.