TWISTED Longest common subsequence

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?

Answers


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.


Need Your Help

Setting up umbraco

iis umbraco

hello i am trying to set up umbraco on my pc