比较字符串列表的最佳数据结构和算法是什么？

Question

我想找到与以下规则相匹配的最长可能的单词顺序：

• 每个单词最多可以一次使用
• 所有单词都是字符串
• 两个字符串 sa 和 sb 如果最后两个字符 sa 匹配的前两个字符 sb.

在串联的情况下，它是通过重叠这些字符来执行的。例如：

• SA =“ Torino”
• SB =“ Novara”
• sa concat sb =“ torinovara”

例如，我有以下输入文件“ input.txt”：

诺瓦拉

都灵

Vercelli

拉文纳

那不勒斯

利文诺

弥赛亚

Noviligure

罗马

并且，根据上述规则的上述文件的输出应为：

都灵

诺瓦拉

拉文纳

那不勒斯

Livorno

Noviligure

由于最长的串联是：

torinovaravennapolivornovilligure

有人可以帮我吗？最佳的数据结构是什么？

Answer 1

这可以作为定向图问题表示 - 节点是单词，如果它们重叠（选择最小的重叠以获得最长的长度），它们会被边缘连接，然后找到最高的重量非交流路径。

（嗯，实际上，您需要将图表扩展到以词的开始和结尾。与每个重量长度词 / 2的边缘相邻的“启动节点”。 +长度完成 / 2，每个单词和“ ending节点”“长度单词 / 2”之间。将其加倍可能更容易。）

https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-path-path-in-weighted-graph

Answer 2

我会开始很简单。制作2个字符串的向量，一个正常分类，一个用最后2个字母排序。为第二个向量创建一个指出其在第一个方面的位置的索引（INT的向量）。

找到最长的..首先删除孤儿。两者都不匹配的单词。那你想建立一个 邻居加入 树，您可以确定哪些单词可以彼此到达。如果您有2棵或更多树，则应首先尝试最大的树。

现在，有了一棵树，您的工作就是找到罕见的目的，并将其绑定到其他目的，然后重复。如果它使用金色的所有单词，请跳过其他树，这应该为您提供一个很好的解决方案。如果不是这样，那么您将进入一系列算法以使其有效。

需要考虑的一些项目：如果您有3个以上的唯一目的，则可以保证丢弃1个以上的单词。这可以用来修剪寻找答案时的尝试。经常重新计算独特的目的。给定端的奇数确保必须丢弃一个（您的末端获得2个免费赠品）。隔离可以自我匹配的单词，您可以随时将它们扔到最后，否则它们会弄脏数学。您也许可以创建小的自我匹配戒指，只要您在创建它们时不孤儿，就可以像自我匹配的单词一样对待这些戒指。这可以使性能奇妙，但不能保证完美的解决方案。

搜索空间是顺序（n！），可能很难证明一个数百万个元素的列表。当然，我可能会忽略一些东西。