ac1187.pas

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

program tju1187;
const
  maxfiles=250;
  maxlen=8;
  c:string[63]='?0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
type
  list=array[1..maxfiles]of byte;
var
  a:array[1..maxfiles]of string[8];
  plus:array[1..maxfiles]of boolean;
  count:array['0'..'z']of word;
  ok:array[1..maxfiles,0..maxlen,0..maxlen]of boolean;
  index:list;
  n,m,total,i,j:byte;
  st:string;
  ch:char;
function match(s:string;t,start:byte):boolean;
  var
    ls,lt,i,j,k:byte;
  begin
    ls:=length(s);lt:=length(a[t]);
    for i:=start to ls do
      if s[i]='*' then begin
        ok[t,i,0]:=ok[t,i-1,0];
        for j:=1 to lt do
          ok[t,i,j]:=ok[t,i-1,j] or ok[t,i,j-1]
      end
      else begin
        for j:=lt downto 1 do
          ok[t,i,j]:=ok[t,i-1,j-1] and (s[i] in ['?',a[t,j]]);
        ok[t,i,0]:=false;
      end;
    match:=ok[t,ls,lt];
  end;
procedure try(s:string;start:byte);
  var
    tindex:list;
    tn,tm,i,l:byte;
  begin
    if length(s)>8 then exit;
    tn:=n;tm:=m;tindex:=index;
    n:=0;m:=0;
    for i:=1 to tn do
      if match(s,index[i],start) then begin
        inc(n);index[n]:=index[i];
        if plus[index[i]] then inc(m);
      end;
    l:=length(s);
    if (m>total) or (m=total) and (l<length(st)) then begin
      if n=m then begin total:=n;st:=s;end;
      if s[l]='*' then begin
        delete(s,l,1);
        for i:=1 to 63 do begin
          if count[c[i]]<=total then break;
          try(s+c[i],l);
          try(s+c[i]+'*',l+1);
          if i>1 then begin
            try(s+'*'+c[i],l);
            try(s+'*'+c[i]+'*',l+2);
          end;
        end;
      end;
    end;
    n:=tn;m:=tm;index:=tindex;
  end;
begin
  repeat
    fillchar(count,sizeof(count),0);count['?']:=maxint;
    n:=0;m:=0;
    repeat
      readln(st);
      if st='*' then break;
      inc(n);
      a[n]:=copy(st,1,length(st)-2);
      plus[n]:=st[length(st)]='+';
      if plus[n] then begin
        inc(m);
        for i:=1 to length(a[n]) do
          inc(count[a[n,i]]);
      end;
    until false;

    for i:=2 to 62 do
      for j:=i+1 to 63 do
        if count[c[i]]<count[c[j]] then begin
          ch:=c[i];c[i]:=c[j];c[j]:=ch;
        end;

    fillchar(ok,sizeof(ok),0);
    for i:=1 to n do begin
      index[i]:=i;ok[i,0,0]:=true;
    end;
    total:=0;st:='';
    try('*',1);
    writeln(total);
  until seekeof;
end.