An O(n2log⁡m)-time algorithm for the boxed-mesh permutation pattern matching problem

Given a text T of length n and a pattern P of length m over a numeric alphabet Σ, the boxed-mesh permutation pattern matching problem is to find all boxed-subsequences of T whose relative order between all characters is the same as that of P. In this paper, we propose an O(n2log⁡m)-time algorithm for the boxed-mesh permutation pattern matching problem based on interesting properties of boxed subsequences, using preprocessed information on P and order-statistic trees.