最长公共子序列N序列(为不同目的)
最长公共子序列N序列(为不同目的)
提问于 2017-11-01 11:32:23
我想找出N个字符串最长的公共子序列。我得到了对两个字符串使用动态规划的算法，但是如果将它扩展到N，它将消耗大量的内存，因为我需要一个N维数组。这不是一种选择。
在普通情况下(90%)，几乎所有字符串都是相同的。
如果我试图在N/2对中分解N个序列，每个两个字符串分别运行2个字符串的LCS，我将有N/2个子序列。我可以删除重复，并重复这个过程，直到我只有一个子序列，这是常见的所有字符串在输入。
我遗漏了什么吗？它看起来不像是一个解决N难题的方法.
我知道每对字符串对LCS的调用都可能有多个子序列作为解决方案，但是如果我在下一次调用中只使用其中一个子序列作为输入，也许我的最后一个子序列不是最长的，但我有一些可能适合我的需要。
如果我尝试对一对使用所有可能的解，然后将其与来自另一对的所有可能的解(其中每对都可能有多个)结合起来，我可能会以指数时间结束。我说的对吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-11-01 11:45:46
是的，您错过了正确性:不能保证一对字符串的LCS与整个集合的LCS有任何重叠。考虑一下这个例子：
aaabb1xyz
aaabb2xyz
cccdd1xyz
cccdd2xyz如果按照给定的顺序对它们，您将得到aaabb和cccdd的LCS，缺少集合的xyz。
如果，正如您所说的，字符串几乎都是相同的，那么也许这些差异对您来说并不是一个问题。如果不相同的字符串与“中位数”字符串非常相似，那么增量解决方案就可以满足您的需要。
另一种可能是对随机字符串进行LCS，直到中间字符串出现为止；然后从这个公共点开始，您应该有一个“足够好”的解决方案。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/47062351
复制相关文章
点击加载更多
相似问题
从故事板访问按钮
访问样式的按钮故事板
如何在Swift +故事板中按项目名访问splitViewItems
以编程方式访问故事板按钮？
如何绘制按钮故事板？
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
