Question

单词接龙！！（信息学的题）要广搜 有Free Pascal

题四 单词接龙 (36分)

问题描述：
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们己知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙" 中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

输入:
输入的第一行为一个单独的整数n(n<=20）表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表来“龙”开头的字母。你可以假定以此字母开头的“龙" 一定存在。

输出:
只需输出以此字母开头的最长的“龙”的长度

样例:

输入
5
at
touch
cheat
choose
tact
a

输出
23 （连成的“龙”为atoucheatactactouchoose

Answer 1

单词接龙是求最长的串，所以用广搜显然没有深搜优，时间，空间，以及编写的复杂度均比深搜大，以下是我用深搜通过的代码，稍微改了些东西，如果有错的话或者需要解释请说明一下，我再改一下。
program jielong;
var a:array[1..20]of string;
bo:array[1..20]of integer;
t,k,m,n,j,max:longint;
c:char;
s:string;
g:text;
function dui1(i:integer;s:string;var st:string):boolean;
var t,k:longint;
o,p:string;
begin
dui1:=false;
if length(s)>length(a[i]) then k:=length(a[i])
else k:=length(s);
for t:=length(s) downto length(s)-k+1 do
if s[t]=a[i][1] then
begin
o:=copy(s,t,length(s)-t+1);
p:=copy(a[i],1,length(s)-t+1);
if o=p then
begin
st:=copy(s,1,t-1)+a[i];
if st<>s then dui1:=true;
if dui1 then exit;
end;
end;
end;

procedure sou(s:string);
var t,k:integer;
o:string;
begin
k:=0;
for t:=1 to n do
begin
if (bo[t]<2)and dui1(t,s,o) then
begin
inc(k);
inc(bo[t]);
sou(o);
dec(bo[t]);
end;
end;
if k=0 then if max<length(s) then max:=length(s);
end;

begin
readln(n);
for t:=1 to n do
readln(a[t]);
read(s);
for t:=1 to n do
if a[t][1]=s then
begin
inc(bo[t]);
sou(a[t]);
dec(bo[t]);
end;
writeln(max);
end.

Answer 2

program word_dragon(input,output);
const maxn=20;
type node=record
state:array [1..maxn] of integer;{state为每个单词的引用数}
last,len:integer; {last记录龙中最后一个单词的序号，len记录龙的长度}
end;
var i,j,n,p1,p2,head,tail,len,maxlen:integer;
first:char; find:boolean;
word:array [1..maxn] of string; {word是提供的单词表}
link:array [1..maxn,1..maxn] of integer;
q:array [1..2300] of node;{q为龙队列}
begin
write('input word number:'); readln(n);
for i:=1 to n do readln(word[i]);
write('input first letter:'); readln(first);
for i:=1 to n do {计算单词与单词的连接关系,即求link}
for j:=1 to n do
begin
link[i,j]:=0;
find:=false;
len:=1;
while (len<length(word[i])) and (len<length(word[j])) and (not (find)) do
begin
p1:=length(word[i])-len+1;
p2:=1;
while (p1<=length(word[i])) and (word[i,p1]=word[j,p2]) do
begin
p1:=p1+1; p2:=p2+1;
end;
if p1>length(word[i]) then find:=true else len:=len+1;
end;
if find then link[i,j]:=length(word[j])-len
end; {for}
tail:=1;
for i:=1 to n do
if word[i,1]=first then
with q[tail] do
begin
for j:=1 to n do state[j]:=0;
state[i]:=1; last:=i;
len:=length(word[i]); tail:=tail+1;
end; {with}
head:=1;
while head<tail do {宽度搜索开始}
begin
for i:=1 to n do {尝试在队首元素之后接上第i个单词}
if (q[head].state[i]<2) and (link[q[head].last,i]>0) then
with q[tail] do {将新元素添加到队尾}
begin
for j:=1 to n do state[j]:=q[head].state[j];
state[i]:=state[i]+1;
last:=i; tail:=tail+1;
len:=q[head].len+link[q[head].last,i];
end; {with}
head:=head+1;
end; {while}
maxlen:=q[1].len;
for i:=2 to tail-1 do
if maxlen<q[i].len then maxlen:=q[i].len;
writeln(maxlen);
end.