题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。

在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。

我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。

样例

输入：5
at
touch
cheat
choose
tact
a
输出：23

算法1（AC）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int link[1001][1001];
int ans;
char c[30][1001];
int n;
int tme[1001];
int tmp_len;
char begin_char;
void dfs(int cur)
{
    tme[cur]++;//使用次数
    for(int i=1;i<=n;i++)
        if(tme[i]<2&&link[cur][i]!=-1)
        {
            int temp=strlen(c[i])-link[cur][i];//加上单词i的长度。但是重叠部分被算了2次，所以减掉1次。注意此处应为局部变量。若为全局变量，则变量的值会变化。
            if(temp)
            {
                tmp_len+=temp;
                dfs(i);
                tmp_len-=temp;//回溯
            }
        }
    ans=max(tmp_len,ans);
    tme[cur]--;//回溯
} 
int main()
{
    bool is_find,is_find2;
    int i_len,j_len;
    int maxrep;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    cin>>begin_char;
    //首先，预处理出两两单词能否连接
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            is_find=0;
            i_len=strlen(c[i]);
            j_len=strlen(c[j]);
            maxrep=min(i_len,j_len);//重叠部分的长度显然不能超过单词的长度
            for(int k=1;k!=maxrep;k++)//枚举接龙重叠部分长度 
            {
                is_find2=true;          
                for(int l=1;l<=k;l++)//一个一个位置判断两个单词是否能连接
                {
                    if(c[i][i_len-k+l-1]!=c[j][l-1])
                    {
                        is_find2=false;//只要有一个位置不一样，就不能连接
                        break;
                    }
                }
                if(is_find2)
                {
                    link[i][j]=k;
                    is_find=true;//两个单词可以拼到一起
                    break;//为了使龙的长度大，我们要使连接的部位长度小，所以break即可。
                }
            }
            if(!is_find)//两个单词不能拼到一起
                link[i][j]=-1;
        }
    }
    for(int i=1;i<=n;i++)
        if(c[i][0]==begin_char)
        {
            tmp_len=strlen(c[i]);//第i个单词开始
            dfs(i);
        }
    cout<<ans<<'\n';
    return 0;
}