PersonalCorpus 版 (精华区)

149209 14:33:01 1 Mar 2002
Bozhang,HIT,P.R.China 1002 Pascal Accepted 2.403 sec 712K


const p:array['a'..'z'] of char=('2','2','2','3','3','3','4','4','1',
'1','5','5','6','6','0','7','0','7','7','8','8','8','9','9','9','0');
var
    s:array[1..50000] of string;
    cost:array[0..100] of byte;
    used:array[0..100] of word;
    from:array[0..100] of byte;
    i,j,k,m,n,tots:integer;
    num,temp:string;
    res:array[1..100] of word;
begin
    readln(num);
    while num<>'-1' do begin
        readln(tots);
        for i:=1 to tots do readln(s[i]);
        for i:=1 to tots do begin
            j:=1;
            while j<=length(s[i]) do if (s[i,j]<'a') or (s[i,j]>'z')
then delete(s[i],j,1) else inc(j);
        end;
(*        for i:=1 to tots-1 do for j:=i+1 to tots do if
length(s[i])<length(s[j]) then begin
            temp:=s[i]; s[i]:=s[j]; s[j]:=temp;
        end;
  *)
        fillchar(cost,sizeof(cost),255); cost[0]:=0;
        fillchar(used,sizeof(used),0);
        fillchar(from,sizeof(from),0);
        for i:=1 to length(num) do begin
            n:=i;
            for j:=0 to i-1 do
                for k:=1 to tots do if length(s[k])=i-j then begin
                    for m:=1 to length(s[k]) do if p[s[k,m]]<>num[m+j]
then break;
                    if m>length(s[k]) then if cost[j]<cost[n] then begin
 n:=j; used[i]:=k; break end;
                end;
            if used[i]=0 then cost[i]:=255 else begin
                from[i]:=n;cost[i]:=cost[n]+1;
            end;
        end;
        if cost[length(num)]=255 then writeln('No solution.')else
begin
            i:=1; j:=length(num); res[1]:=used[j];
            while from[j]<>0 do begin
                j:=from[j]; inc(i); res[i]:=used[j];
            end;
            for j:=i downto 2 do write(s[res[j]],' ');
writeln(s[res[1]]);
        end;
        readln(num);
    end;
end.