English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a pattern of length $m$ and a text of length $n$, the goal in$k$-mismatch pattern matching is to compute, for every $m$-substring of thetext, the exact Hamming distance to the pattern or report that it exceeds $k$.This can be solved in either $\widetilde{O}(n \sqrt{k})$ time as shown by Amiret al. [J. Algorithms 2004] or $\widetilde{O}((m + k^2) \cdot n/m)$ time due toa result of Clifford et al. [SODA 2016]. We provide a smooth time trade-offbetween these two bounds by designing an algorithm working in time$\widetilde{O}( (m + k \sqrt{m}) \cdot n/m)$. We complement this with amatching conditional lower bound, showing that a significantly fastercombinatorial algorithm is not possible, unless the combinatorial matrixmultiplication conjecture fails.

Optimal trade-offs for pattern matching with $k$ mismatches