Pattern matching for permutations
Given a permutation T of 1 to n, and a permutation P of 1 to k, for k ≤ n, we wish to find a k-element subsequence of T whose elements are ordered according to the permutation P. For example, if P is (1,2,⋯,k), then we wish to find an increasing subsequence of length k in T; this special case can be done in time O(n log log n) [CW].We prove that the general problem is NP-complete. We give a polynomial time algorithm for the decision problem, and the corresponding counting problem, in the case that P is separable—i.e. contains neither the subpattern (3, 1, 4, 2) nor its reverse, the subpattern (2, 4, 1, 3).
|Series||Lecture Notes in Computer Science|
Bose, P, Buss, J.F. (Jonathan F.), & Lubiw, A. (Anna). (1993). Pattern matching for permutations. In Lecture Notes in Computer Science.