2026-07-24T17:25:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6074 2024-03-06T10:37:35Z ddc:004 open_access

Boxed Permutation Pattern Matching Amit, Mika Bille, Philip Hagge Cording, Patrick Li Gørtz, Inge Wedel Vildhøj, Hjalte Permutation Subsequence Pattern Matching Order Preserving Boxed Mesh Pattern Given permutations T and P of length n and m, respectively, the Permutation Pattern Matching problem asks to find all m-length subsequences of T that are order-isomorphic to P. This problem has a wide range of applications but is known to be NP-hard. In this paper, we study the special case, where the goal is to only find the boxed subsequences of T that are order-isomorphic to P. This problem was introduced by Bruner and Lackner who showed that it can be solved in O(n^3) time. Cho et al. [CPM 2015] gave an O(n^2m) time algorithm and improved it to O(n^2 log m). In this paper we present a solution that uses only O(n^2) time. In general, there are instances where the output size is Omega(n^2) and hence our bound is optimal. To achieve our results, we introduce several new ideas including a novel reduction to 2D offline dominance counting. Our algorithm is surprisingly simple and straightforward to implement. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Amit and Philip Bille and Patrick Hagge Cording and Inge Li Gørtz and Hjalte Wedel Vildhøj 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.20 urn:nbn:de:0030-drops-60744 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.20 eng https://creativecommons.org/licenses/by/3.0/legalcode