A permutation P = (p1, p2, ... , pk) of 1 to k is called a pattern of the permutation T = (t1, t2, ... ,tn) of 1 to n, if and only if there is a length k subsequence T' of T such that the elements of T' are ordered according to the permutation P. The longest common permutation problem is of finding the longest pattern which is involved in two permutations π1 and π2. In this paper, we give a O(n6) time algorithm to find the longest common permutation between two permutations when one permutation is separable. Our results improve the Bouvel’s O(n8) time algorithm in [2].
