ac1175.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1175;
const
  maxwords=10000;
var
  w:array[1..maxwords]of string;
  a,pre:array[1..maxwords]of word;
  last:array[0..26]of word;
  t,u,n,i,l,r,m:longint;
  s1,s2:ansistring;
  c:char;
procedure sort(s,t,p:word);
  var
    fin:array[0..26]of word;
    i,x:word;
  begin
    if s>=t then exit;
    for i:=s to t do begin
      if length(w[a[i]])<p then x:=0 else x:=ord(w[a[i]][p])-96;
      pre[a[i]]:=last[x];last[x]:=a[i];
    end;
    i:=s-1;
    for x:=0 to 26 do begin
      while last[x]>0 do begin
        inc(i);a[i]:=last[x];last[x]:=pre[last[x]];
      end;
      fin[x]:=i;
    end;
    for x:=1 to 26 do
      sort(fin[x-1]+1,fin[x],p+1);
  end;
begin
  read(t);
  for u:=1 to t do begin
    readln(n);
    for i:=1 to n do begin
      readln(w[i]);a[i]:=i;
    end;
    sort(1,n,1);

    repeat
      s1:='';s2:='';
      repeat
        read(c);
        s1:=s1+c;if c in ['a'..'z'] then s2:=s2+c;
      until eoln or (c=' ');
      l:=1;r:=n;
      repeat
        m:=(l+r) shr 1;
        if s2=w[a[m]] then break;
        if s2<w[a[m]] then r:=m-1 else l:=m+1;
      until l>r;
      if l>r then
        write(s1)
      else
        for i:=1 to length(s1) do
          if s1[i] in ['a'..'z'] then write('*') else write(s1[i]);
    until eoln;
    writeln;
  end;
end.