题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词

且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次）

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

另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

输入

输入的第一行为一个单独的整数n(n≤20)表示单词数

以下n行每行有一个单词（只含有大写或小写字母，长度不超过20）

输入的最后一行为一个单个字符，表示“龙”开头的字母。

你可以假定以此字母开头的“龙”一定存在。

输出

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

样例

输入

5
at
touch
cheat
choose
tact
a

输出

23

样例解释

连成的“龙”为 atoucheatactactouchoose

分析及代码实现

大致步骤

• 输入
• 从开始的字符判断有没有能接到的龙
• 如果有字符串能接到，则接上去
• 算出接龙后的长度
• 找到所有接龙情况中的最大值

C++代码实现

#include 
#include 
#include 
using namespace std;

int n, length = 0, vis[1000] = {0};
string str[1000];

//返回a,b之中可以首尾相接的长度（长度越短，相接后的字符串越长）
    //此处有两个特判
    //一种是没有重合长度，要返回0
    //另一种是两个字符串中长度最小的长度为1，会直接返回0
inline int check(string a, string b){
    int p = min(a.length(), b.length());
    for (int i = 1; a.length() == 1 ? i <= p : i < p; i++){
        bool flag = true;
        for (int j = 0; j < i; j++)
            if (a[a.length() - i + j] != b[j]){
                flag = false;
                break;
            }
        if (flag == true)   return i;
    }
    return 0;
}

//用dfs从1到n判断这些字符串能不能接上去
    //（只要看两个字符串有没有重叠部分就可以了）
void dfs(string s, int length_now){
    length = max(length, length_now);// 算出所有接龙情况中的最长长度
    for (int i = 1; i <= n; i++){
        if (vis[i] > 1)    continue;
        else{
            int add = check(s, str[i]);
            if (add != 0){
                vis[i]++;
                //接龙长度 = 龙的长度 + 现在接上的长度 - 重合的长度
                dfs(str[i], length_now + str[i].length() - add);
                vis[i]--;//恢复现场
            }
        }
    }
}


int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> str[i];
    cin >> str[n + 1];//“龙头”
    
    dfs(str[n + 1], 1);
    
    cout << length << endl;
    return 0;
}