dev*_*ast 4 c algorithm directed-graph digraphs data-structures
我想找到符合以下规则的最长的单词序列:
sa和sb级联,如果最后两个字符sa匹配的前两个字符sb.在连接的情况下,通过重叠这些字符来执行.例如:
例如,我有以下输入文件"input.txt":
诺瓦拉
都灵
维切利
拉文纳
那不勒斯
liverno
messania
诺维利古雷
罗马
并且,根据上述规则输出的上述文件应为:
都灵
诺瓦拉
拉文纳
那不勒斯
利沃诺
诺维利古雷
因为最长的连接是:
torinovaravennapolivornovilligure
有人可以帮我解决这个问题吗？什么是最好的数据结构？
这可以表示为有向图问题 - 节点是单词,如果它们重叠,它们通过边连接(并且选择最小重叠以获得最长的长度),然后找到最高权重的非交叉路径.
(嗯,实际上,你想要稍微扩展一下图形来处理一个单词的开头和结尾.加上一个"起始节点",带有一个边缘到重量长度字/ 2的每个单词.在单词之间,-overlap + length start +长度结束/ 2,以及每个单词和"结束节点""长度单词/ 2"之间.可能更容易加倍.)
https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-path-in-weighted-graph