TY - JOUR
TI - Finding pattern matchings for permutations
DO - https://doi.org/doi:10.7282/T3MC93J9
AU - Ibarra, Louis
PY - 1995-01
AB - Given a permutation P of {1,...., k} and T of {1,...., n}, the pattern matching problem for permutations 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.
LA - English
ER -