language: en

Finding pattern matchings for permutations

Louis Ibarra
Dept. of Computer Science Hill Center, Busch Campus Rutgers University
Piscataway, NJ 08855
ibarra@paul.rutgers.edu January 19, 1995

Abstract Given a permutation P of f1; : : : ; kg and T of f1; : : : ; ng, the pattern matching problem for per mutations is to determine whether there is a length k subsequence of T whose elements are ordered in the same way as the elements of P . We present an O(kn 4 ) time and O(kn 3 ) space algorithm for finding a match of P into T or determining that no match exists, given that P is separable, i.e. contains neither (2, 4, 1, 3) nor (3, 1, 4, 2) as a subpattern.

1 Introduction