string - Twisted 最长公共子序列

Question

我想知道最长公共子序列问题的一个特例 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem 如果我们有两个 n 符号字符串，并且保证它们都只有 1 个符号并且每个符号来自字母表的前 n 个符号。普通算法如何改进？

Answer 1

您要求排列之间的最长公共子序列。与您链接的动态编程相比，有一种改进，称为 Robinson-Schensted-Knuth 算法，它运行时间为 O(n lg n)。在本课程的第 7 和第 8 讲中有一个相当简单的例子来说明它是如何工作的，这里有一个更完整但更复杂的解释。