Back to research

arXiv ยท January 2026

Permutation Matching Under Parikh Budgets

Linear-time detection, packing, and disjoint selection for jumbled-pattern matching by MD Nazmul Alam Shanto, Md. Tanzeem Rahat, and Md. Manzurul Hasan.

Problem

Given a pattern and a text over a general alphabet, decide whether the text contains a window whose Parikh vector matches the pattern, then solve packing and disjoint-selection variants.

Why It Matters

Parikh-vector matching connects string algorithms with resource budgets, frequency constraints, and optimization tasks that appear beyond plain exact pattern detection.

Core Idea

Maintain the Parikh-vector difference between the pattern and the current window, then use sliding-window and greedy interval structure for the associated variants.

Main Result

The paper presents O(n + sigma)-time and O(sigma)-space detection and packing algorithms, plus linear-time disjoint selection after match enumeration.

What Was Difficult

The useful abstraction is seeing symbol counts not only as a matching condition, but also as a supply budget for exact packing.

Open Directions

  • Which approximate or weighted budget variants remain linear?
  • Can the packing view simplify other Abelian pattern-matching tasks?
  • How should these primitives be exposed in reusable string-algorithm libraries?