【记录 | 字符串、搜索】单词接龙

[NOIP2000 提高组] 单词接龙

题目背景

注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。

本题为搜索题，本题不接受 hack 数据。

• 点击查看本题链接
• 关于此类题目的详细内容

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 $n$ 表示单词数，以下 $n$ 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

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

样例 #1

样例输入 #1

5
at
touch
cheat
choose
tact
a

样例输出 #1

23

提示

样例解释：连成的“龙”为 atoucheatactactouchoose。

$n\le 20$。

参考代码

整体思路

1. 首先，计算所有单词对之间的最小重叠长度。为后续的深度优先搜索（DFS）做准备。

2. 然后，从第一个单词开始，找到所有以指定字母开头的单词，作为DFS的起点。

3. 对于每个起点，进行DFS，寻找最长的单词接龙路径。在DFS过程中，我们需要记录每个单词的使用次数，以确保每个单词最多被使用两次。

4. 在DFS过程中，我们还需要更新当前路径的长度。当我们找到一个可以接龙的单词时，我们将这个单词的长度减去它与前一个单词的重叠部分，就得到了新的路径长度。

5. 如果我们遍历完所有的单词都没有找到可以接龙的单词，就说明当前路径是一个完整的单词接龙路径。这时，我们需要检查这个路径的长度是否比已知的最长路径更长，如果是，就更新最长路径的长度。

6. 最后，输出最长路径的长度，就是这个问题的答案。

单词最小重叠部分

在这道题中，我们定义了一个函数 minOverlap，用于计算两个单词之间的最小重叠部分。该函数接收两个参数，x和y，分别代表两个单词在数组中的索引。

int minOverlap(int x, int y) {
   
    bool match = true;
    int yIndex = 0;
    for (int xIndex = words[x].size() - 1; xIndex >= 0; xIndex--) {
   
        for (int k = xIndex; k < words[x].size(); k++) {
   
            if (words[x][k] != words[y][yIndex++]) {
   
                match = false;
                break;
            }
        }
        if (match) {
   
            return words[x].size() - xIndex;
        }
        yIndex = 0;
        match = true;
    }
    return 0;
}

求解步骤如下：

• 函数从单词 x 的最后一个字符开始，逐个向前遍历。
• 在每次遍历中，函数会检查单词 x 从当前字符开始到最后一个字符，是否和单词 y 从第一个字符开始的部分完全匹配。
• 如果在比较过程中发现有不匹配的字符，就将match设置为false并跳出内部循环。
• 如果单词 x 的一部分和单词 y 的开头部分完全匹配，函数就返回这部分的长度，即words[x].length() - xIndex。
• 如果函数遍历完单词 x 的所有字符都没有找到匹配的部分，就返回 0，表示两个单词没有重叠部分。

有了这个 minOverlap 函数预处理后，我们就可以开始对字符串数组进行搜索了。

深度优先搜索

下面这个 dfs() 函数的目的是找到最长的单词接龙路径：

void dfs(int p) {
   
    bool found = false;
    for (int j = 0; j < n; j++) {
   
        if (used[j] >= 2 || overlap[p][j] == 0 || overlap[p][j] == words[p].