dorsal/arxiv
View SchemaPermutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection
| Authors | MD Nazmul Alam Shanto, Md. Tanzeem Rahat, Md. Manzurul Hasan |
|---|---|
| Categories | |
| ArXiv ID | 2601.09577vv1 |
| URL | https://arxiv.org/abs/2601.09577 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
We study permutation (jumbled/Abelian) pattern matching over a general alphabet $\Sigma$. Given a pattern P of length m and a text T of length n, the classical task is to decide whether T contains a length-m substring whose Parikh vector equals that of P . While this existence problem admits a linear-time sliding-window solution, many practical applications require optimization and packing variants beyond mere detection. We present a unified sliding-window framework based on maintaining the Parikh-vector difference between P and the current window of T , enabling permutation matching in O(n + {\sigma}) time and O({\sigma}) space, where {\sigma} = |{\Sigma}|. Building on this foundation, we introduce a combinatorial-optimization variant that we call Maximum Feasible Substring under Pattern Supply (MFSP): find the longest substring S of T whose symbol counts are component-wise bounded by those of P . We show that MFSP can also be solved in O(n + {\sigma}) time via a two-pointer feasibility maintenance algorithm, providing an exact packing interpretation of P as a resource budget. Finally, we address non-overlapping occurrence selection by modeling each permutation match as an equal-length interval and proving that a greedy earliest-finishing strategy yields a maximum-cardinality set of disjoint matches, computable in linear time once all matches are enumerated. Our results provide concise, provably correct algorithms with tight bounds, and connect frequency-based string matching to packing-style optimization primitives.
{
"annotation_id": "ccf50814-9983-40d4-8a0d-9f59c8f416bb",
"date_created": "2026-02-17T05:53:19.964000Z",
"date_modified": "2026-02-17T05:53:19.964000Z",
"file_hash": "21fa91dfa09d506a0dcb768b871c54252b10a687c7daaecd4e2f8a3ad88df464",
"private": false,
"record": {
"abstract": "We study permutation (jumbled/Abelian) pattern matching over a general alphabet $\\Sigma$. Given a pattern P of length m and a text T of length n, the classical task is to decide whether T contains a length-m substring whose Parikh vector equals that of P . While this existence problem admits a linear-time sliding-window solution, many practical applications require optimization and packing variants beyond mere detection. We present a unified sliding-window framework based on maintaining the Parikh-vector difference between P and the current window of T , enabling permutation matching in O(n + {\\sigma}) time and O({\\sigma}) space, where {\\sigma} = |{\\Sigma}|. Building on this foundation, we introduce a combinatorial-optimization variant that we call Maximum Feasible Substring under Pattern Supply (MFSP): find the longest substring S of T whose symbol counts are component-wise bounded by those of P . We show that MFSP can also be solved in O(n + {\\sigma}) time via a two-pointer feasibility maintenance algorithm, providing an exact packing interpretation of P as a resource budget. Finally, we address non-overlapping occurrence selection by modeling each permutation match as an equal-length interval and proving that a greedy earliest-finishing strategy yields a maximum-cardinality set of disjoint matches, computable in linear time once all matches are enumerated. Our results provide concise, provably correct algorithms with tight bounds, and connect frequency-based string matching to packing-style optimization primitives.",
"arxiv_id": "2601.09577",
"authors": [
"MD Nazmul Alam Shanto",
"Md. Tanzeem Rahat",
"Md. Manzurul Hasan"
],
"categories": [
"cs.DS",
"cs.CL"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection",
"url": "https://arxiv.org/abs/2601.09577",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "539082c6-650b-44be-8465-31a22b029289",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}