EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes

Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, Florin Manea

Theory of Computing Systems · 2018-01 · 62 (1) · 162-191

DOI: 10.1007/s00224-017-9794-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theory of Computing Systems, online erschienen am 15.08.2017. Verfasst von Paweł Gawrychowski und 4 weiteren Autor:innen. Die Arbeit wurde bisher 21-mal zitiert (Crossref) und nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: DFG.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

An α-gapped repeat (α ≥ 1) in a word w is a factor uvu of w such that |uv| ≤ α|u|; the two occurrences of u are called arms of this α-gapped repeat. An α-gapped repeat is called maximal if its arms cannot be extended simultaneously with the same character to the right nor to the left. We show that the number of all maximal α-gapped repeats occurring in words of length n is upper bounded by 18αn. In the case of α-gapped palindromes, i.e., factors uvu⊺\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$uv{{u}^{\intercal }}$\end{document} with |uv|≤ α|u|, we show that the number of all maximal α-gapped palindromes occurring in words of length n is upper bounded by 28αn + 7n. Both upper bounds allow us to construct algorithms finding all maximal α-gapped repeats and/or all maximal α-gapped palindromes of a word of length n on an integer alphabet of size nO(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n^{\mathcal {O}(1)}$\end{document} in O(αn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathcal {O}(\alpha n)}$\end{document} time. The presented running times are optimal since there are words that have Θ(αn) maximal α-gapped repeats/palindromes.

Förderung

  • DFG

Zitieren

APA

Gawrychowski, P., I, T., Inenaga, S., Köppl, D., & Manea, F. (2018). Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes. Theory of Computing Systems, 62(1), 162-191. https://doi.org/10.1007/s00224-017-9794-5

Vancouver

Gawrychowski P, I T, Inenaga S, Köppl D, Manea F. Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes. Theory of Computing Systems. 2018;62(1):162-191. doi:10.1007/s00224-017-9794-5

BibTeX
@article{Gawrychowski2018,
  author = {Gawrychowski, Paweł and I, Tomohiro and Inenaga, Shunsuke and Köppl, Dominik and Manea, Florin},
  title = {Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes},
  journal = {Theory of Computing Systems},
  year = {2018},
  volume = {62},
  number = {1},
  pages = {162--191},
  doi = {10.1007/s00224-017-9794-5}
}
Kostenlos starten →