我想找到符合以下规则的最长可能的单词序列:
- 每个词最多只能使用一次
- 所有单词都是字符串
- 如果
sa的最后两个字符与sb< 的前两个字符匹配，则可以连接两个字符串。sa和sb/
在连接的情况下，它是通过重叠这些字符来执行的。例如:
- sa = "都灵"
- sb = "诺瓦拉"
- sa concat sb = "torinovara"
例如，我有以下输入文件“input.txt”:
novara
torino
vercelli
ravenna
napoli
liverno
messania
noviligure
roma
并且，根据上述规则，上述文件的输出应该是:
torino
novara
ravenna
napoli
livorno
noviligure
因为最长可能的连接是:
torinovaravennapolivornovilligure
谁能帮我解决这个问题？最好的数据结构是什么？
最佳答案
这可以表示为一个有向图问题——节点是单词，如果它们重叠(并且选择最小重叠以获得最长长度)，则它们通过边连接，然后找到权重最高的非-交叉路径。
(好吧，实际上，您想稍微扩展图形以处理单词的开头和结尾。连接一个“起始节点”，每个单词的权重长度为 word/2。 单词之间，-overlap + length start + length finish/2，以及每个单词和一个“ending node”之间的“length word/2”。加倍可能更容易。)
https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-path-in-weighted-graph
关于c - 比较字符串列表的最佳数据结构和算法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4529872/