倍捻最长公共子

Question

我想知道的最长公共子序列的一个特例 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem 如果我们有N个符号的两个字符串和保证他们两人恰好有1个符号和前n每一个符号字母表的符号。 如何改善正常算法？

Answer 1

你在问排列之间最长的公共子序列。对链接的动态编程有一个改进，称为Robinson-Schensted-Knuth算法，它运行时间为O（n lg n）。有一个相当简单的例子，它是如何工作的in Lectures 7 & 8 of this course，以及更完整但涉及的解释here。