题三． 单词接龙 （27分）
问题描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
输 入
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输 出
只需输出以此字母开头的最长的“龙”的长度
样 例 ：
输入
5
at
touch
cheat
choose
tact
a
输出
23 （连成的“龙”为atoucheatactactouchoose）
【思路】
回溯法。
可以离线求出j接在i之后的重叠部分c[i][j]，这样就可以把序列的尾巴u以及序列的长度len作为状态搜索，否则还要以string为状态搜索。
【代码】
#include<iostream>
#include<cstring>
using namespace std; const int maxn = +;
int n;
int c[maxn][maxn];
int x[maxn],A[maxn]; //标记//序列
string words[maxn];
int wordslen[maxn];
int ans=; //计算a前b后的重叠长度
//substr截取字符串
int calc(string a,string b) {
int lena=a.size(),lenb=b.size();
int len=min(lena,lenb);
for(int l=;l<=len-;l++) { //len-1不能包含 //且重叠部分尽量小 从小到大枚举
if(a.substr(lena-l,l)==b.substr(,l))
return l;
}
return ;
} void dfs(int u,int len) {
ans=max(ans,len);
for(int v=;v<n;v++) if(x[v]< && c[u][v]) {
x[v]++;
dfs(v,len+wordslen[v]-c[u][v]);
x[v]--;
}
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<n;i++){
cin>>words[i]; wordslen[i]=words[i].size();
}
for(int i=;i<n;i++) for(int j=;j<n;j++) //自己可能与自己重叠
c[i][j]=calc(words[i],words[j]);
char ch; cin>>ch;
for(int i=;i<n;i++) if(words[i][]==ch) {
x[i]++; dfs(i,wordslen[i]); x[i]--;
}
cout<<ans;
return ;
}