An O (n(2) log 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 Sigma, 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 (n(2) login)-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. (C) 2017 Elsevier B.V. All rights reserved.