想讨论算法，没有代码。
问题:设S和T是两个元素序列。找出它们之间保持元素顺序的公共子序列。
它应该有O(n + m)的运行时间，其中n是S的长度，m是t的长度。我还想假设这两个序列在大多数情况下是相似的。
一个最优解?:经过一些研究，一个似乎是最优的解决方案是首先为两个序列构建一个通用后缀树。然后找到最长的公共子串，并将此子序列视为解决方案的一部分。然后，要么从树中删除该子序列，要么用从两个原始序列中删除的子序列构建一个新的后缀树，以形成S'和T'。然后找出S'和T'之间最长的公共子串，以此类推。
为了分析运行时间，构建树需要O(n)，您可以在O(n + m)中找到S和T的最长公共子串的长度和起始位置。
是否有其他人知道或可以链接到的其他(更)实用的解决方案?有没有发表过关于相同或相关问题的论文?对上述解决方案的意见和建设性的批评?谢谢你的宝贵时间!
我的第一个想法是使用后缀树，并将其与LCS问题联系起来。但我不知道有什么更好的解决办法。我快速搜索了一下，发现了一些可能有用的论文和项目，但不能保证。
http://dl.acm.org/citation.cfm?id=1625377(我相信这里有直接链接:http://www.aaai.org/Papers/IJCAI/2007/IJCAI07-101.pdf)
http://code.google.com/p/all-common-subsequences/很抱歉，这是漫长的一天，我没有足够的清醒来尝试更好的解决方案。