Document Open Access Logo

Computing the Antiperiod(s) of a String

Authors Hayam Alamro, Golnaz Badkobeh, Djamal Belazzougui, Costas S. Iliopoulos, Simon J. Puglisi

PDF
Thumbnail PDF

File

LIPIcs.CPM.2019.32.pdf
  • Filesize: 424 kB
  • 11 pages

Document Identifiers

Author Details

Hayam Alamro
  • Department of Informatics, King’s College London, UK
  • Department of Information Systems, Princess Nourah bint Abulrahman University, Riyadh, KSA
Golnaz Badkobeh
  • Department of Computing, Goldsmiths, University of London, UK
Djamal Belazzougui
  • Centre de Recherche sur I'nformation Scientifique et Technique, Algeria
Costas S. Iliopoulos
  • Department of Informatics, King’s College London, UK
Simon J. Puglisi
  • Department of Computer Science, University of Helsinki, Finland

Acknowledgements

This work was supported by the Academy of Finland under grant 319454. We thank the anonymous reviewers for their detailed comments that greatly improved the quality of this article, in particular for the improvement in Section 5.2 and for pointers on previous works on weighted-level ancestors data structures.

Cite AsGet BibTex

Hayam Alamro, Golnaz Badkobeh, Djamal Belazzougui, Costas S. Iliopoulos, and Simon J. Puglisi. Computing the Antiperiod(s) of a String. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 32:1-32:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CPM.2019.32

Abstract

A string S[1,n] is a power (or repetition or tandem repeat) of order k and period n/k, if it can be decomposed into k consecutive identical blocks of length n/k. Powers and periods are fundamental structures in the study of strings and algorithms to compute them efficiently have been widely studied. Recently, Fici et al. (Proc. ICALP 2016) introduced an antipower of order k to be a string composed of k distinct blocks of the same length, n/k, called the antiperiod. An arbitrary string will have antiperiod t if it is prefix of an antipower with antiperiod t. In this paper, we describe efficient algorithm for computing the smallest antiperiod of a string S of length n in O(n) time. We also describe an algorithm to compute all the antiperiods of S that runs in O(n log n) time.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • antiperiod
  • antipower
  • power
  • period
  • repetition
  • run
  • string

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Golnaz Badkobeh, Gabriele Fici, and Simon J. Puglisi. Algorithms for Anti-Powers in Strings. Information Processing Letters, 137:57-60, 2018. URL: http://arxiv.org/abs/1805.10042.
  2. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "Runs" Theorem. SIAM J. Comput., 46(5):1501-1514, 2017. Google Scholar
  3. Carl Barton, Tomasz Kociumaka, Chang Liu, Solon P Pissis, and Jakub Radoszewski. Indexing weighted sequences: neat and efficient. arXiv preprint, 2017. URL: http://arxiv.org/abs/1704.07625.
  4. Amanda Burcroff. (k,λ)-Anti-Powers and Other Patterns in Words. Electronic Journal of Combinatorics, 25(4):#P4.41, 2018. Google Scholar
  5. Maxime Crochemore, Lucian Ilie, and Liviu Tinta. The "runs" conjecture. Theor. Comput. Sci., 412(27):2931-2941, 2011. Google Scholar
  6. Maxime Crochemore and Wojciech Rytter. Jewels of Stringology. World Scientific, 2002. Google Scholar
  7. Colin Defant. Anti-Power Prefixes of the Thue-Morse Word. Electronic Journal of Combinatorics, 24(1):#P1.32, 2017. Google Scholar
  8. Martin Farach and S Muthukrishnan. Perfect hashing for strings: Formalization and algorithms. In Annual Symposium on Combinatorial Pattern Matching, pages 130-140. Springer, 1996. Google Scholar
  9. Gabriele Fici, Antonio Restivo, Manuel Silva, and Luca Q. Zamboni. Anti-Powers in Infinite Words. In 43rd International Colloquium on Automata, Languages, and Programming, (ICALP), volume 55 of LIPIcs, pages 124:1-124:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  10. Gabriele Fici, Antonio Restivo, Manuel Silva, and Luca Q. Zamboni. Anti-powers in infinite words. J. Comb. Theory, Ser. A, 157:109-119, 2018. URL: http://dx.doi.org/10.1016/j.jcta.2018.02.009.
  11. Harold N Gabow and Robert Endre Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of computer and system sciences, 30(2):209-221, 1985. Google Scholar
  12. Marisa Gaetz. Anti-power j-fixes of the Thue-Morse word. URL: http://arxiv.org/abs/1808.01528.
  13. Paweł Gawrychowski. Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic. In European Symposium on Algorithms, pages 421-432. Springer, 2011. Google Scholar
  14. Paweł Gawrychowski. Personal Communication, 2018. Google Scholar
  15. Paweł Gawrychowski, Moshe Lewenstein, and Patrick K Nicholson. Weighted ancestors in suffix trees. In European Symposium on Algorithms, pages 455-466. Springer, 2014. Google Scholar
  16. Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997. Google Scholar
  17. Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. A Linear Time Algorithm for Seeds Computation. arXiv preprint, 2011. URL: http://arxiv.org/abs/1107.2422.
  18. Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Efficient representation and counting of antipower factors in words. In International Conference on Language and Automata Theory and Applications, pages 421-433. Springer, 2019. Google Scholar
  19. Roman M. Kolpakov, Ghizlane Bana, and Gregory Kucherov. mreps: efficient and flexible detection of tandem repeats in DNA. Nucleic Acids Research, 31(13):3672-3678, 2003. Google Scholar
  20. Roman M. Kolpakov and Gregory Kucherov. Finding Maximal Repetitions in a Word in Linear Time. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 596-604, 1999. Google Scholar
  21. Tsvi Kopelowitz and Moshe Lewenstein. Dynamic weighted ancestors. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 565-574. Society for Industrial and Applied Mathematics, 2007. Google Scholar
  22. M. Lothaire. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002. URL: http://dx.doi.org/10.1017/CBO9781107326019.
  23. Shyam Narayanan. Functions on antipower prefix lengths of the Thue-Morse word. URL: http://arxiv.org/abs/1705.06310.
  24. W. F. Smyth. Computing Patterns in Strings. Pearson Addison Wesley, United Kingdom, 2003. Google Scholar
  25. Axel Thue. Uber unendliche Zeichenreihen. Norske vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana, 7:1-22, 1906. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact