Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection

• URL: http://arxiv.org/abs/2601.09577v1
• Date: Wed, 14 Jan 2026 15:46:45 GMT
• Title: Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection
• Authors: MD Nazmul Alam Shanto, Md. Tanzeem Rahat, Md. Manzurul Hasan,
• Abstract summary: We study permutation (jumbled/Abelian) pattern matching over a general alphabet $$.<n>We present a unified sliding-window framework based on maintaining the Parikh-vector difference between P and the current window of T.<n>We show that MFSP can also be solved in O(n + ) time via a two-pointer feasibility maintenance algorithm.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study permutation (jumbled/Abelian) pattern matching over a general alphabet $Σ$. 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 + σ) time and O(σ) space, where σ = |Σ|. 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 + σ) 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.

Related papers

• Fairness in Repeated Matching: A Maximin Perspective [13.603504120117016]
  We study a sequential decision-making model where a set of items is repeatedly matched to the same set of agents over multiple rounds.<n>The objective is to determine a sequence of matchings that either maximizes the utility of the least advantaged agent at the end of all rounds (optimal) or at the end of every individual round (anytime optimal)
  arXiv  Detail & Related papers  (2025-10-06T09:32:40Z)
• Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations [10.282294365033785]
  We show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time.<n>We present a new model that allows analyzing non-adaptive preprocessing algorithms for a wide array of search and decision problems.
  arXiv  Detail & Related papers  (2025-05-01T22:17:11Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We present a novel characterization of rank, grounded in the well-known Transformer architecture.<n>We show that the rank of a function $f$ corresponds to the minimum number of emphChain of Thought steps required by a single-layer Transformer.<n>We also introduce the notion of the multi-head rank that captures multi-head single-layer transformers, and perform the analysis of PAC-learnability of the classes of functions with bounded multi-head rank.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Probabilistic Permutation Graph Search: Black-Box Optimization for Fairness in Ranking [53.94413894017409]
  We present a novel way of representing permutation distributions, based on the notion of permutation graphs. Similar to PL, our distribution representation, called PPG, can be used for black-box optimization of fairness.
  arXiv  Detail & Related papers  (2022-04-28T20:38:34Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Random Intersection Chains [0.0]
  We propose a method that selects interactions of categorical features, called Random Intersection Chains. It uses random intersections to detect frequent patterns, then selects the most meaningful ones among them. We show that if the number and length of chains are appropriately chosen, the patterns in the tail nodes are indeed the most frequent ones in the data set.
  arXiv  Detail & Related papers  (2021-04-10T08:41:15Z)
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem [0.5584060970507505]
  We design a derivation technique to tackle a few problems over maximal matchings in graphs. We get a superposition over all possible matchings when given the empty state as input and a superposition over all maximal matchings when given the W -states as input. Our main result is that the expected size of the matchings corresponding to the output states of our QAOA+ algorithm when ran on a 2-regular graph is greater than the expected matching size obtained from a uniform distribution over all matchings.
  arXiv  Detail & Related papers  (2020-11-24T06:36:11Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Infinite Feature Selection: A Graph-based Feature Filtering Approach [78.63188057505012]
  We propose a filtering feature selection framework that considers subsets of features as paths in a graph. Going to infinite allows to constrain the computational complexity of the selection process. We show that Inf-FS behaves better in almost any situation, that is, when the number of features to keep are fixed a priori.
  arXiv  Detail & Related papers  (2020-06-15T07:20:40Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.