python/TangDou/AcWing/SearchOrder/1117.md

AcWing 1117. 单词接龙

一、题目描述

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

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

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

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

输入格式 输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示 龙 开头的字母。

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

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

数据范围 n≤20，单词随机生成。

输入样例：

5
at
touch
cheat
choose
tact
a

输出样例：

23

提示 连成的 龙 为 atoucheatactactouchoose。

二、解题思路

• 遍历所有单词，找出 开头字母 是 给定开始字母 的单词，它们都有可能是第一个单词
• 假设选择的第一个单词是A,那么需要逐个考查所有单词（也包括A自己），是不是可以拼接在当前单词A的后面，也就是 开头 与 结尾 存在 相同的子串。如果存在不同长度的子串，比如abdcd与dcdab,那么我们需要选择最短的子串，因为这样才能保证最后拼接的长度最长（贪心）
• 我们需要记录 每个单词 的　出现次数，因为题目要求最多不能超过两次

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int n;
string word[N];
int cnt[N];
int res;

int getSameLength(string a, string b) {
    for (int i = 1; i < min(a.size(), b.size()); i++)
        if (a.substr(a.size() - i, i) == b.substr(0, i))
            return i;
    return 0;
}

void dfs(int u, string str) {
    res = max((int)str.size(), res); // 不断刷新龙的长度

    // 记录该字符串使用次数
    for (int i = 0; i < n; i++) { // 遍历所有字符串，找出可以接在u后面串
        int len = getSameLength(word[u], word[i]);
        // 最小公共长度（可以保证龙最长），并且，使用次数小于2次
        // 最小公共长度对于后面的串而言，也是前缀位置
        if (len && cnt[i] < 2) {
            cnt[i]++;
            dfs(i, str + word[i].substr(len));
            cnt[i]--;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> word[i];

    char st;
    cin >> st;

    for (int i = 0; i < n; i++) // 枚举每个字符串
        // 如果该字符串的首字母是指定的起点字母st
        if (word[i][0] == st) {
            cnt[i]++;
            dfs(i, word[i]); // 开始将当前搜索到的字符串作为首串开始深搜
            cnt[i]--;
        }

    cout << res << endl; // 最大长度
    return 0;
}