【题目来源】
洛谷：[P1019 NOIP 2000 提高组] 单词接龙 - 洛谷 (luogu.com.cn)
【题目描述】
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。
【输入】
输入的第一行为一个单独的整数 \(n\) 表示单词数，以下 \(n\) 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
【输出】
只需输出以此字母开头的最长的“龙”的长度。
【输入样例】
5
at
touch
cheat
choose
tact
a
【输出样例】
23
【解题思路】
【算法标签】
《洛谷 P1019 单词接龙》 #字符串# #搜索# #NOIP提高组# #2000#
【代码详解】
#include <bits/stdc++.h> // 包含所有标准库头文件
using namespace std;int n; // 单词数量
int mark[25] = {0}; // 记录每个单词使用次数（最多使用2次）
int ans = 0; // 记录最长字符串长度
char c; // 起始字符
string ss[25], s; // ss[]存储所有单词，s为临时字符串// 拼接函数：找到两个字符串的最大重叠部分并拼接
string pj(string s1, string s2)
{int len1 = s1.length(), len2 = s2.length();// 从最小重叠长度1开始尝试，直到其中一个字符串的长度for (int i = 1; i < len1 && i < len2; i++) {// 检查s1的后i位是否等于s2的前i位if (s1.substr(len1 - i, i) == s2.substr(0, i)) {// 返回拼接后的字符串（去掉重叠部分）return s1.substr(0, len1 - i) + s2;}}return "0"; // 没有重叠部分返回"0"
}// 深度优先搜索函数
void dfs(string drag)
{// 更新最大长度if (drag.length() > ans) ans = drag.length();// 尝试所有可能的单词for (int i = 1; i <= n; i++) {// 如果单词已使用2次则跳过if (mark[i] == 2) continue;// 尝试拼接当前字符串和单词is = pj(drag, ss[i]);if (s != "0") // 如果可以拼接{mark[i]++; // 标记单词i使用次数+1dfs(s); // 递归处理拼接后的字符串mark[i]--; // 回溯，恢复使用次数}}
}int main()
{// 输入单词数量cin >> n;// 输入所有单词for (int i = 1; i <= n; i++) cin >> ss[i];// 输入起始字符cin >> c;// 遍历所有单词，找到以c开头的单词作为起点for (int i = 1; i <= n; i++) if (ss[i][0] == c) { // 如果单词以c开头mark[i]++; // 标记使用次数+1dfs(ss[i]); // 开始深度优先搜索mark[i]--; // 回溯，恢复使用次数}// 输出最长字符串长度cout << ans << endl;return 0;
}
【运行结果】
5
at
touch
cheat
choose
tact
a
23