An O (n(2) log m)-time algorithm for the boxed-mesh permutation pattern matching problem

作者：Cho Sukhyeun; Na Joong Chae^*; Sim Jeong Seop

来源：Theoretical Computer Science, 2018, 710: 35-43.

DOI：10.1016/j.tcs.2017.02.022

• Permutation pattern matching
• Order-isomorphism
• Boxed-mesh pattern

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.

• 出版日期2018-2-1