divword.pas

本光盘是《国际大学生程序设计竞赛例题解（一）》的配套光盘

program Divide_Word;
type
  ws=string[20];
var
  f:text;
  found:boolean;
  c,x,m:array[2..20] of integer;
  {c[i]表示长度为i的单词的个数  x[i]表示当前解的第i个分量  m[i]表示当前第i个分量已找到的最小解}
  s:array[1..1000] of ws;  {单词表}
  l:byte;
  n:word;

procedure init;  {初始化}
var
  f:text;
  i:word;
begin
  assign(f,'divword.dat');reset(f);
  readln(f,l);
  readln(f,n);
  fillchar(c,sizeof(c),0);
  for i:=1 to n do
    begin
      readln(f,s[i]);
      inc(c[length(s[i])]);
    end;
  close(f);
  for i:=2 to 20 do m[i]:=1000;
  found:=false;
end;

function preckok:boolean;  {判断是否满足M + Ｘ <= C}
var i:byte;
begin
  preckok:=true;
  for i:=2 to 20 do
    begin
      if m[i]+x[i]>c[i] then preckok:=false;
      if x[i]<m[i] then m[i]:=x[i];
    end;
end;

procedure precheck(k,left:integer);  {判断无解，k表示第k个解，left表示剩余字串的长度}
var i:integer;
begin
  if (k=21) or found then exit;  {找完20个解分量就回溯}
  if left=0 then  {剩余字串的长度为0时就判断是否符合要求}
    begin
      if preckok then found:=true;  {判断是否满足M + Ｘ <= C}
      exit;
    end;
  x[k]:=0;  {先令第k个解分量为0}
  precheck(k+1,left);
  for i:=1 to c[k] do if (not found) and (left>=k) then
    begin
      dec(left,k);x[k]:=i;
      precheck(k+1,left);  {递归找下一个解分量}
    end;
end;

procedure find;  {搜索}
var
  qq:array[1..50] of byte;  {qq[i]表示总第i步是搜索第qq[i]个字符串}
  mk:array[1..1000] of boolean;  {单词已用标记}
  t:array[1..2] of string[50];  {t[q]表示第q个字符串}
  w:array[1..2,1..25] of word;  {w[q,i]表示第q个字符串第i步搜索时用到的单词编号}
  m:array[1..2] of byte;  {m[q]表示第q个字符串组成的单词数}
  p:array[1..2,0..25] of byte;  {p[q,i]表示第q个字符串第i步搜索时的字符串长度}
  df:ws;  {两个字符串的差距部分}
  q,i:byte;  {q: 当前这步搜索是对第q个字符串进行  i:当前搜索的总步数}
  re:boolean;
  function match(var s1,s2:ws):boolean;  {判断s1是否与s2匹配，即一个字符串是另一个字符串的前缀}
  var i:byte;
  begin
    if (p[1,m[1]-1]<l+1) and (p[2,m[2]-1]<l+1) and (length(s1)=length(s2)) then
     {搜索中不能出现两个字符串长度相等，除非都等于待求字符串长度L}
      begin match:=false;exit end;
    i:=1;
    while (i<=length(s1)) and (i<=length(s2)) and (s1[i]=s2[i]) do inc(i);
    if (i<=length(s1)) and (i<=length(s2)) then match:=false else match:=true;
  end;
begin
  fillchar(qq,sizeof(qq),0);
  fillchar(mk,sizeof(mk),0);
  fillchar(w,sizeof(w),0);
  fillchar(p,sizeof(p),0);
  m[1]:=1;m[2]:=1;
  t[1]:='';t[2]:='';
  p[1,0]:=1;p[2,0]:=1;
  i:=1;
  repeat
    if p[1,m[1]-1]>p[2,m[2]-1] then q:=2 else q:=1;  {对短的字符串搜索}
    qq[i]:=q;
    df:=copy(t[3-q],p[q,m[q]-1],p[3-q,m[3-q]-1]-p[q,m[q]-1]+1);  {求两个字符串的差距部分}
    repeat
      re:=false;
      inc(w[q,m[q]]);
      if w[q,m[q]]>n then  {回溯}
        begin
          w[q,m[q]]:=0;re:=true;
          dec(i);if i=0 then exit;
          q:=qq[i];
          dec(m[q]);
          delete(t[q],p[q,m[q]-1],p[q,m[q]]-p[q,m[q]-1]+1);
          mk[w[q,m[q]]]:=false;
          if p[1,m[1]-1]>p[2,m[2]-1] then q:=2 else q:=1;
          df:=copy(t[3-q],p[q,m[q]-1],p[3-q,m[3-q]-1]-p[q,m[q]-1]+1);
        end;
      if (not re) and mk[w[q,m[q]]] then re:=true;  {不允许重复单词}
      if (not re) and (df<>'') and (not match(df,s[w[q,m[q]]])) then re:=true;  {判断差距部分df是否与当前尝试的单词匹配}
    until not re;
    t[q]:=t[q]+s[w[q,m[q]]];
    p[q,m[q]]:=p[q,m[q]-1]+length(s[w[q,m[q]]]);
    mk[w[q,m[q]]]:=true;
    inc(m[q]);
    inc(i);
    if (p[1,m[1]-1]>l+1) or (p[2,m[2]-1]>l+1) or ((p[1,m[1]-1]=l+1) and (p[2,m[2]-1]=l+1)) then  {长度大于等于L则回溯}
      begin
        if (p[1,m[1]-1]=l+1) and (p[2,m[2]-1]=l+1) then  {找到解}
          begin
            writeln(f,t[1]);
            close(f);
            halt;
          end;
        delete(t[q],p[q,m[q]-2],p[q,m[q]-1]-p[q,m[q]-2]+1);
        mk[w[q,m[q]-1]]:=false;
        dec(m[q]);
        dec(i);
      end
  until false;
end;

begin  {主程序}
  init;  {初始化}
  assign(f,'divword.out');rewrite(f);
  precheck(2,l);  {判断无解}
  if found then find;  {如果有解则进入搜索}
  writeln(f,'NO SOLUTION');
  close(f);
end.