題目描述 單詞接龍是一個與我們經常玩的成語接龍相類似的游戲，現在我們已知一組單詞，且給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍”中出現兩次），在兩個單詞相連時，其重合部分合為一部分，例如 beast和astonish，如果接成一條龍則變為beastonish，另外相鄰的兩部分不能存在包含關系，例如at 和 atide 間不能相連。
輸入輸出格式 輸入格式： 輸入的第一行為一個單獨的整數n (n<=20)表示單詞數，以下n 行每行有一個單詞，輸入的最后一行為一個單個字符，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在。
輸出格式： 只需輸出以此字母開頭的最長的“龍”的長度
輸入輸出樣例 輸入樣例#1： 5 at touch cheat choose tact a 輸出樣例#1： 23 （連成的“龍”為atoucheatactactouchoose）
說明 這一題要用到回溯，會簡單些。
程序如下：
var a:array[1..20] of string; b,c:array[1..20] of longint; l,n,max:longint; s:string;PRocedure dfs(head:string);var k,j,i:byte; s1,s2:string;begin for i:=1 to n do if c[i]<2 then begin s:=a[i]; if length(head)>=b[i] then k:=b[i]-1 else k:=length(head); s1:=''; s2:=''; for j:=1 to k do begin s1:=head[length(head)+1-j]+s1; s2:=s2+s[j]; if s1=s2 then begin l:=l+b[i]-j; if l>max then max:=l; inc(c[i]); dfs(a[i]); dec(c[i]); l:=l+j-b[i]; end; end; end;end;begin readln(n); for l:=1 to n do begin readln(s); a[l]:=s; b[l]:=length(s); end; readln(s); l:=length(s); dfs(s); writeln(max);end.新聞熱點
疑難解答
