题目描述

奶牛们正在前往明尼苏达州的湖泊旅行。和其他人一样，它们感到无聊，于是玩起了“旅行游戏”来打发时间。

在这个旅行游戏中，第一头奶牛从神圣旅行游戏词典（STGD）中想出一个三个字母的单词。队伍中的下一头奶牛必须在这个单词的开头、两个字母之间或者结尾添加一个字母，从而形成神圣旅行游戏词典中的另一个单词。奶牛们想知道最终能形成的单词最大长度是多少。

给定一个包含 D（1 <= D <= 1000）个单词的词典和一个起始单词，找出在这个旅行游戏中能够形成的任意一个最长的单词。

输入

• 第 1 行：整数 D，后面跟一个空格，再跟一个合法的三个字母的单词。
• 第 2 行到第 D + 1 行：每行包含一个来自神圣旅行游戏词典的合法单词，长度不超过 80 个字符，仅由小写字母组成。

输出

一行，包含通过扩展输入的起始单词能够形成的最长单词。

输入数据保证正确结果是唯一的。

示例输入

9 cal
cal
calf
calfs
call
calls
choral
chorale
coal
coral

示例输出

chorale

提示

[形成的单词序列为：cal, coal, coral, choral, chorale]

来源

USACO 2003 年 2 月 Orange 组

题意分析

奶牛们在旅行途中玩一种单词接龙游戏。游戏规则为：从一个给定的三个字母的单词开始，后续奶牛每次可以在当前单词的开头、中间任意位置或者结尾添加一个字母，使得新形成的单词也在给定的词典里。目标是根据给定的词典和起始的三个字母单词，找出按照此规则能形成的最长单词。

解题思路

1. 数据存储：先读取词典中单词的数量 D 和起始的三个字母单词。接着将词典中的所有单词存储起来，方便后续查找。
2. 构建图关系：把每个单词看作图中的一个节点，若一个单词可以通过在另一个单词基础上添加一个字母得到，就在这两个单词对应的节点间连一条有向边。
3. 深度优先搜索（DFS）或广度优先搜索（BFS）：以起始单词为起点，在构建好的图里进行搜索。不断扩展路径，也就是不断尝试在当前单词基础上添加字母形成新单词，直到无法继续扩展。在搜索过程中，记录找到的最长单词。
4. 输出结果：搜索结束后，输出找到的最长单词。

算法标签

• 图论：将单词接龙问题转化为图的搜索问题，通过构建图来表示单词之间的关系。
• 搜索算法：可使用深度优先搜索（DFS）或广度优先搜索（BFS）在图中搜索最长路径，进而找出最长的单词。

• 代码实现

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include<sstream>
#include<cctype>
#include<cfloat>
#include <set>
#include<queue>
#include <map>
#include <iomanip>
using namespace std;
set<string> st;
string s[1110];
  string s1,s2,s3;
    string S;
int cmp(string a,string b)//按字符串长度从大到小排序
{
     return a.size()>b.size();
 
}
bool dfs(string ss)
{
    if(ss==S) return 1;
    bool r=0;
    int L=ss.size();
    for(int i=0;i<L;++i)//去掉一个字符，枚举
    {
        s1=ss.substr(0,i);
        s2=ss.substr(i+1,L-i-1);
        s3=s1+s2;
        if(st.count(s3))  r = dfs(s3);//如果去掉一个字符后仍在字符串序列中 继续dfs
        if(r==1) break;//一开始忘记加这句，一直WA，不加这句可能会导致被后面的false覆盖true
    }
    if(r==1 ) return 1;
    else   return 0;
}
int main()
{
   //freopen("input.txt","r",stdin);
   int T,n,m;
   cin>>T;
 
   cin>>S;
   for(int i=1;i<=T;++i)
   {
       cin>>s[i];
       st.insert(s[i]);
   }
   sort(s+1,s+T+1,cmp);
   for(int i=1;i<=T;++i)
   {
       if(dfs(s[i])) {
        cout<<s[i];break;
       }
   }
 
}