type
  node=record
         ch:array['a'..'z'] of longint;
         link:longint;
  end;

var trie:array[1..1000000] of node;
    en,fo:array[1..100000] of string;
    n,p,l:longint;
    st:string;

procedure insert(s:string);
  var r,i:longint;

  begin
    r:=1;
    for i:=1 to length(s) do
      if trie[r].ch[s[i]]=0 then
        begin
          l:=l+1;
          trie[r].ch[s[i]]:=l;
          r:=l;
        end
      else
        r:=trie[r].ch[s[i]];
    trie[r].link:=n;
  end;

function find(s:string):string;
  var r,i:longint;

  begin
    r:=1;
    for i:=1 to length(s) do
      if trie[r].ch[s[i]]<>0 then
        r:=trie[r].ch[s[i]]
      else
       exit('eh');
    exit(en[trie[r].link]);
  end;

begin
  n:=0;
  l:=1;
  readln(st);
  while length(st)>=1 do
    begin
      n:=n+1;
      p:=pos(' ',st);
      en[n]:=copy(st,1,p-1);
      fo[n]:=copy(st,p+1,length(st)-p);
      insert(fo[n]);
      readln(st);
    end;
  while not(eof) do
    begin
      readln(st);
      writeln(find(st));
    end;
end.

• Re:Trie水过~~Memory 63552KB~~ (32) szxyj 2011-03-26 15:57:40