TWISTED Longest common subsequence

Question

I was wondering about a special case of the Longest Common Subsequence problem http://en.wikipedia.org/wiki/Longest_common_subsequence_problem What if we have two strings of n symbols and its guaranteed that both of them have exactly 1 symbol and every symbol from the first n symbols of an alphabet. How can the normal algorithm be improved?

Answer 1

You're asking for the longest common subsequence between permutations. There is an improvement over the dynamic programming one you linked called the Robinson-Schensted-Knuth algorithm, and it runs in time O(n lg n). There's a reasonably simple example of how it works in Lectures 7 & 8 of this course, and a much more complete but involved explanation here.