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?
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.