We introduce Attractor Matching, a new framework for structural string comparison built upon the theory of string attractors. Given a pattern x of length m and one of its attractors Γx, the problem asks for all substrings y[i.. i+m-1] of a text y such that Γx is also an attractor of y[i.. i+m-1]. Unlike classical notions of string matching, which rely on character equality or distance measures, attractor matching focuses on the structural properties that govern repetitiveness and compressibility. Our contribution is fourfold. First, we adapt the IsAttractor algorithm of Béal et al. by combining the DAWG with the slidingwindow technique of Blumer, enabling online attractor verification as the window advances over the text. Second, we reformulate the verification procedure on the Compressed DAWG (CDAWG), obtaining a more compact representation that preserves correctness. Third, we employ the sliding-window CDAWG method of Inenaga et al., which allows efficient attractor matching on sliding-window maintained CDAWGs with incremental updates. Finally, we introduce a relaxed variant, Attractor Matching with Mismatches, where the pattern attractor may be extended by at most ρ additional positions, enabling structurally tolerant matching. This paradigm bridges compression and similarity, opening new directions for structure-aware pattern matching.
Attractor Matching: A New Paradigm for Structural String Comparison
Faro S.;Marino F. P.
2026-01-01
Abstract
We introduce Attractor Matching, a new framework for structural string comparison built upon the theory of string attractors. Given a pattern x of length m and one of its attractors Γx, the problem asks for all substrings y[i.. i+m-1] of a text y such that Γx is also an attractor of y[i.. i+m-1]. Unlike classical notions of string matching, which rely on character equality or distance measures, attractor matching focuses on the structural properties that govern repetitiveness and compressibility. Our contribution is fourfold. First, we adapt the IsAttractor algorithm of Béal et al. by combining the DAWG with the slidingwindow technique of Blumer, enabling online attractor verification as the window advances over the text. Second, we reformulate the verification procedure on the Compressed DAWG (CDAWG), obtaining a more compact representation that preserves correctness. Third, we employ the sliding-window CDAWG method of Inenaga et al., which allows efficient attractor matching on sliding-window maintained CDAWGs with incremental updates. Finally, we introduce a relaxed variant, Attractor Matching with Mismatches, where the pattern attractor may be extended by at most ρ additional positions, enabling structurally tolerant matching. This paradigm bridges compression and similarity, opening new directions for structure-aware pattern matching.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
