首页 > 试题广场 >

[NOIP2000]单词接龙

[编程题][NOIP2000]单词接龙
  • 热度指数：689 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

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


输出描述:
只需输出以此字母开头的最长的“龙”的长度
示例1

输入

5
at
touch
cheat
choose
tact
a

输出

23

说明

连成的“龙”为atoucheatactactouchoose
算法知识视频讲解
添加回答
C/C++
梦樱羽头像 梦樱羽
注意点：1.前缀和后缀的公共部分应该选最短的。2.如果两个字符串前缀和后缀的公共部分恰好是其中一个字符串，那么这两个字符串不能合并。
发表于 2019-04-08 14:49:03 回复(0)
提交观点

问题信息

深度优先搜索(DFS) NOIP复赛
难度：
1条回答 5403浏览

热门推荐

通过挑战的用户

相关试题

[NOIP2000]单词接龙

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号