我想找到符合以下规则的最长的单词序列：
sa则两个字符串sb可以连接起来。sasb在连接的情况下，它是通过重叠这些字符来执行的。例如：
例如，我有以下输入文件“input.txt”：
诺瓦拉
都灵
韦尔切利
拉文纳
那不勒斯
利弗诺
弥赛亚
新人
罗马
并且，根据上述规则，上述文件的输出应该是：
都灵
诺瓦拉
拉文纳
那不勒斯
里窝那
新人
因为最长可能的连接是：
torinovaravennapolivornovilligure
谁能帮我解决这个问题？最好的数据结构是什么？
这可以表示为一个有向图问题——节点是单词，如果它们重叠则通过一条边连接（并且选择最小的重叠以获得最长的长度），然后找到权重最高的非相交路径.
（好吧，实际上，您想稍微扩展一下图形以处理一个单词的开头和结尾。将“起始节点”与每个权重长度 word / 2 的单词相邻。单词之间，-overlap + length start +长度完成/ 2，以及在每个单词和“结束节点”之间“长度单词/ 2”。可能更容易加倍。）
https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-path-in-weighted-graph
我会开始很简单。制作 2 个字符串向量，一个按正常排序，一个按最后 2 个字母排序。为第二个向量创建一个索引（整数向量），指出它在第一个向量中的位置。
要找到最长的..首先删除孤儿。两端不匹配的单词。然后你想建立一个邻居加入树，这是你确定哪些单词可能相互到达的地方。如果您有 2 棵或更多树，则应先尝试最大的树。
现在，对于一棵树，您的工作是找到稀有的末端，并将它们绑定到其他末端，然后重复。这应该会为您提供一个非常好的解决方案，如果它使用您的所有单词，请跳过其他树。如果没有，那么您将使用一整套算法来提高效率。
需要考虑的一些事项：如果您有 3 个以上的独特结尾，则保证会删除 1 个以上的单词。这可用于在寻找答案时减少您的尝试。经常重新计算独特的目的。给定末端的奇数确保必须丢弃一个（末端有 2 个免费赠品）。隔离可以自我匹配的单词，你总是可以把它们放在最后，否则它们会搞砸数学。您也许可以创建小的自匹配环，您可以将它们视为自匹配词，只要您在创建它们时不孤立它们。这可以使性能出色，但不能保证完美的解决方案。
搜索空间是 order(N!) 数百万个元素的列表可能很难证明一个确切的答案。当然，我可能会忽略一些东西。