Document Open Access Logo

Factorizing a String into Squares in Linear Time

Authors Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Florin Manea

PDF
Thumbnail PDF

File

LIPIcs.CPM.2016.27.pdf
  • Filesize: 445 kB
  • 12 pages

Document Identifiers

Author Details

Yoshiaki Matsuoka
Shunsuke Inenaga
Hideo Bannai
Masayuki Takeda
Florin Manea

Cite As Get BibTex

Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Florin Manea. Factorizing a String into Squares in Linear Time. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 27:1-27:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CPM.2016.27

Abstract

A square factorization of a string w is a factorization of w in which each factor is a square. Dumitran et al. [SPIRE 2015, pp. 54-66] showed how to find a square factorization of a given string of length n in O(n log n) time, and they posed a question whether it can be done in O(n) time. In this paper, we answer their question positively, showing an O(n)-time algorithm for square factorization in the standard word RAM model with machine word size omega = Omega(log n). We also show an O(n + (n log^2 n) / omega)-time (respectively, O(n log n)-time) algorithm to find a square factorization which contains the maximum (respectively, minimum) number of squares.

Subject Classification

Keywords
  • Squares
  • Runs
  • Factorization of Strings

Metrics

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

References

  1. Golnaz Badkobeh, Hideo Bannai, Keisuke Goto, Tomohiro I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, and Shiho Sugimoto. Closed factorization. In Proc. PSC 2014, pages 162-168, 2014. Google Scholar
  2. Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, and Shiho Sugimoto. Diverse palindromic factorization is np-complete. In Proc. DLT 2015, volume 9168 of Lecture Notes in Comput. Sci., pages 85-96. Springer, 2015. Google Scholar
  3. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "Runs" Theorem. CoRR, abs/1406.0263, 2014. URL: http://arxiv.org/abs/1406.0263.
  4. Maxime Crochemore. An optimal algorithm for computing the repetitions in a word. Inf. Process. Lett., 12(5):244-250, 1981. Google Scholar
  5. Maxime Crochemore, Lucian Ilie, and William F. Smyth. A simple algorithm for computing the lempel ziv factorization. In Proc. DCC 2008, pages 482-488. IEEE, 2008. Google Scholar
  6. Maxime Crochemore and Wojciech Rytter. Squares, cubes, and time-space efficient string searching. Algorithmica, 13(5):405-425, 1995. URL: http://dx.doi.org/10.1007/BF01190846.
  7. Marius Dumitran, Florin Manea, and Dirk Nowotka. On prefix/suffix-square free words. In Proc. SPIRE 2015, volume 9309 of Lecture Notes in Comput. Sci., pages 54-66. Springer, 2015. Google Scholar
  8. Jean-Pierre Duval. Factorizing words over an ordered alphabet. J. Algorithms, 4(4):363-381, 1983. URL: http://dx.doi.org/10.1016/0196-6774(83)90017-2.
  9. Gabriele Fici, Travis Gagie, Juha Kärkkäinen, and Dominik Kempa. A subquadratic algorithm for minimum palindromic factorization. J. Discrete Algorithms, 28:41-48, 2014. Google Scholar
  10. Jesús García-López, Florin Manea, and Victor Mitrana. Prefix-suffix duplication. J. Comput. Syst. Sci., 80(7):1254-1265, 2014. URL: http://dx.doi.org/10.1016/j.jcss.2014.02.011.
  11. Torben Hagerup. Sorting and searching on the word RAM. In Proc. STACS 1998, volume 1373 of Lecture Notes in Comput. Sci., pages 366-398. Springer, 1998. Google Scholar
  12. Tomohiro I, Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing palindromic factorizations and palindromic covers on-line. In Proc. CPM 2014,, volume 8486 of Lecture Notes in Comput. Sci., pages 150-161. Springer, 2014. Google Scholar
  13. Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323-350, 1977. URL: http://dx.doi.org/10.1137/0206024.
  14. Roman Kolpakov and Gregory Kucherov. Finding maximal repetitions in a word in linear time. In Proc. FOCS 1999, pages 596-604. IEEE, 1999. Google Scholar
  15. Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur. Pal^k is linear recognizable online. In SOFSEM 2015, volume 8939 of Lecture Notes in Comput. Sci., pages 289-301. Springer, 2015. Google Scholar
  16. Manfred Kufleitner. On bijective variants of the Burrows-Wheeler transform. In Proc. PSC 2009, pages 65-79, 2009. Google Scholar
  17. Roger C. Lyndon. On Burnside’s problem. Trans. Amer. Math. Soc., 77(2):202-215, 1954. URL: http://www.jstor.org/stable/1990868.
  18. Michael G. Main and Richard J. Lorentz. An O(n log n) algorithm for finding all repetitions in a string. J. Algorithms, 5(3):422-432, 1984. Google Scholar
  19. James A. Storer and Thomas G. Szymanski. Data compression via textural substitution. J. ACM, 29(4):928-951, 1982. URL: http://dx.doi.org/10.1145/322344.322346.
  20. Terry A. Welch. A technique for high-performance data compression. IEEE Computer, 17(6):8-19, 1984. Google Scholar
  21. Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. IEEE Trans. Information Theory, 23(3):337-343, 1977. Google Scholar
  22. Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE Trans. Information Theory, 24(5):530-536, 1978. 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 About DROPS Imprint Privacy Contact