{"ID":2875382,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.02179","arxiv_id":"2509.02179","title":"Fast Computation of $k$-Runs, Parameterized Squares, and Other Generalised Squares","abstract":"A $k$-mismatch square is a string of the form $XY$ where $X$ and $Y$ are two equal-length strings that have at most $k$ mismatches. Kolpakov and Kucherov [Theor. Comput. Sci., 2003] defined two notions of $k$-mismatch repeats, called $k$-repetitions and $k$-runs, each representing a sequence of consecutive $k$-mismatch squares of equal length. They proposed algorithms for computing $k$-repetitions and $k$-runs working in $O(nk \\log k + output)$ time for a string of length $n$ over an integer alphabet, where $output$ is the number of the reported repeats. We show that $output=O(nk \\log k)$, both in case of $k$-repetitions and $k$-runs, which implies that the complexity of their algorithms is actually $O(nk \\log k)$. We apply this result to computing parameterized squares. A parameterized square is a string of the form $XY$ such that $X$ and $Y$ parameterized-match, i.e., there exists a bijection $f$ on the alphabet such that $f(X) = Y$. Two parameterized squares $XY$ and $X'Y'$ are equivalent if they parameterized match. Recently Hamai et al. [SPIRE 2024] showed that a string of length $n$ over an alphabet of size $σ$ contains less than $nσ$ non-equivalent parameterized squares, improving an earlier bound by Kociumaka et al. [Theor. Comput. Sci., 2016]. We apply our bound for $k$-mismatch repeats to propose an algorithm that reports all non-equivalent parameterized squares in $O(nσ\\log σ)$ time. We also show that the number of non-equivalent parameterized squares can be computed in $O(n \\log n)$ time. This last algorithm applies to squares under any substring compatible equivalence relation and also to counting squares that are distinct as strings. In particular, this improves upon the $O(nσ)$-time algorithm of Gawrychowski et al. [CPM 2023] for counting order-preserving squares that are distinct as strings if $σ= ω(\\log n)$.","short_abstract":"A $k$-mismatch square is a string of the form $XY$ where $X$ and $Y$ are two equal-length strings that have at most $k$ mismatches. Kolpakov and Kucherov [Theor. Comput. Sci., 2003] defined two notions of $k$-mismatch repeats, called $k$-repetitions and $k$-runs, each representing a sequence of consecutive $k$-mismatch...","url_abs":"https://arxiv.org/abs/2509.02179","url_pdf":"https://arxiv.org/pdf/2509.02179v1","authors":"[\"Yuto Nakashima\",\"Jakub Radoszewski\",\"Tomasz Waleń\"]","published":"2025-09-02T10:41:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}