EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Hamming–Levenshtein gap of a string

Monther Alfuraidan, Said Algarni, Othman Echi

RAIRO - Theoretical Informatics and Applications · 2026 · 60 · 19

DOI: 10.1051/ita/2026020 ↗

Kurz gefasst

Fachartikel in der Zeitschrift RAIRO - Theoretical Informatics and Applications, online erschienen am 04.06.2026. Verfasst von Monther Alfuraidan und 2 weiteren Autor:innen. Die Arbeit nennt 5 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Let u , v be strings over an alphabet Σ with |Σ| ≥ 2. Let L ( u , v ) be the Levenshtein distance and, when | u | = | v |, let H ( u , v ) be the Hamming distance. For equal-length strings, L ( u , v ) ≤ H ( u , v ). For u ∈ Σ*, define hl( u ): = max | v |=| u | (H( u , v )−L( u , v )). Ruth and Lladser [ Discrete Math. 346 (2023) Paper No. 113310] showed that if the run-length of u is at most 2, then hl( u ) = 0; conversely, hl( u ) = 0 implies ρ ( u ) ≤ 2. For p ∈ {2, 3}, we characterize all strings u with hl( u ) = | u | – p . We also identify two types of strings u such that hl( u ) = | u | – 4.

Zitieren

APA

Alfuraidan, M., Algarni, S., & Echi, O. (2026). Hamming–Levenshtein gap of a string. RAIRO - Theoretical Informatics and Applications, 60, 19. https://doi.org/10.1051/ita/2026020

Vancouver

Alfuraidan M, Algarni S, Echi O. Hamming–Levenshtein gap of a string. RAIRO - Theoretical Informatics and Applications. 2026;60:19. doi:10.1051/ita/2026020

BibTeX
@article{Alfuraidan2026,
  author = {Alfuraidan, Monther and Algarni, Said and Echi, Othman},
  title = {Hamming–Levenshtein gap of a string},
  journal = {RAIRO - Theoretical Informatics and Applications},
  year = {2026},
  volume = {60},
  pages = {19},
  doi = {10.1051/ita/2026020}
}
Kostenlos starten →