phone.pas

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

program phone(input,output);
const  table:array['a'..'z']of longint
=(1,1,1,2,2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,7,8,8,8,9,9,9);
var   voca:array[1..100]of string;
pass:string;
i,j,k,l,m,n:longint;
data:array[1..100,1..100]of longint;
{ 记录密码串i-j有无解的情况，data[i,j]=-1表示无解，data[i,j]>10000表示第data[i,j]-10000个单词，data[i,j]<10000表示第1个单词与后面分界点位置 }

procedure print(be,en:longint);  {输出}
  var  i:longint;
  begin
    if data[be,en]>10000 then  begin   {be-en本来是一个单词}
                                 if be>1 then write(' ' );
                                 write(voca[data[be,en]-10000]);
                               end
                         else  begin   {是由多个单词组成}
                                 print(be,data[be,en]);
                                 print(data[be,en]+1,en);
                               end;
  end;

function pei(s:string;be,en:longint):boolean;  {判断是否在单词列表中}
  var   i:longint;
  begin
    for i:=be to en do
      begin
        if pass[i]<>char(table[s[i-be+1]]+48) then exit(false);
      end;
    pei:=true;
  end;

procedure qiu(be,en:longint);  {主过程}
  var  i:longint;
  begin
    for i:=1 to n do                       {以下判断是否为一个单词}
      if length(voca[i])=en-be+1 then
        begin
          if pei(voca[i],be,en) then
            begin
              data[be,en]:=10000+i;
              exit;
            end;
        end;
    for i:=be to en-1 do     {以下递推求解}
      begin
        if data[be,i]=0 then qiu(be,i);
        if data[i+1,en]=0 then qiu(i+1,en);
        if (data[be,i]=-1)or(data[i+1,en]=-1) then continue else
          begin
            data[be,en]:=i;
            exit;
          end;
      end;
    data[be,en]:=-1;   {无解}
  end;

begin   {main}
  assign(input,'phone.in');
  assign(output,'phone.out');
  reset(input);rewrite(output);
  readln(n);    {单词表中的单词个数}
  readln(pass);  {密码}
  for i:=1 to n do  {读入n个单词}
    readln(voca[i]);
  qiu(1,length(pass));    {求解}
  if data[1,length(pass)]=-1 then   {无法翻译}
    begin
      writeln('No Solutions!');
      close(output);halt;
    end;
  print(1,length(pass));    {输出一个解}
  close(output);
end.