×

zbMATH — the first resource for mathematics

Longest Lyndon substring after edit. (English) Zbl 07286745
Navarro, Gonzalo (ed.) et al., 29th annual symposium on combinatorial pattern matching, CPM 2018, July 2–4, 2018, Qingdao, China. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-074-3). LIPIcs – Leibniz International Proceedings in Informatics 105, Article 19, 10 p. (2018).
Summary: The longest Lyndon substring of a string \(T\) is the longest substring of \(T\) which is a Lyndon word. \(\operatorname{LLS}(T)\) denotes the length of the longest Lyndon substring of a string \(T\). In this paper, we consider computing \(\operatorname{LLS}(T')\) where \(T'\) is an edited string formed from \(T\). After \(O(n)\) time and space preprocessing, our algorithm returns \(\operatorname{LLS}(T')\) in \(O(\log n)\) time for any single character edit. We also consider a version of the problem with block edits, i.e., a substring of \(T\) is replaced by a given string of length \(l\). After \(O(n)\) time and space preprocessing, our algorithm returns \(\operatorname{LLS}(T')\) in \(O(l\log\sigma+ \log n)\) time for any block edit where \(\sigma\) is the number of distinct characters in \(T\). We can modify our algorithm so as to output all the longest Lyndon substrings of \(T'\) for both problems.
For the entire collection see [Zbl 1390.68025].

MSC:
68W32 Algorithms on strings
Software:
STAR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amihood Amir, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, and Jakub Radoszewski. Longest common factor after one edit operation. In \it String Processing \it and Information Retrieval - 24th International Symposium, SPIRE 2017, Palermo, Italy, \it September 26-29, 2017, Proceedings, pages 14-26, 2017.
[2] Alberto Apostolico and Maxime Crochemore. Fast parallel Lyndon factorization with applications. \it Mathematical Systems Theory, 28(2):89-108, 1995.
[3] Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The “runs” theorem. \it SIAM J. Comput., 46(5):1501-1514, 2017.
[4] Frédérique Bassino, Julien Clément, and Cyril Nicaud. The standard factorization of Lyndon words: an average point of view. \it Discrete Mathematics, 290(1):1-25, 2005.
[5] Michael A. Bender and Martín Farach-Colton. The level ancestor problem simplified. \it TCS, 321(1):5-12, 2004.
[6] Dany Breslauer, Roberto Grossi, and Filippo Mignosi. Simple real-time constant-space string matching. In \it Proc. CPM 2011, pages 173-183, 2011.
[7] Marc Chemillier. Periodic musical sequences and Lyndon words. \it Soft Comput., 8(9):611- 616, 2004.
[8] K. T. Chen, R. H. Fox, and R. C. Lyndon. Free differential calculus. iv. the quotient groups of the lower central series. \it Annals of Mathematics, 68(1):81-95, 1958.
[9] Maxime Crochemore and Dominique Perrin. Two-way string matching. \it J. ACM, 38(3):651- 675, 1991.
[10] Jacqueline W. Daykin, Frantisek Franek, Jan Holub, A. S. M. Sohidull Islam, and W. F. Smyth. Reconstructing a string from its Lyndon arrays. \it Theor. Comput. Sci., 710:44-51, 2018.
[11] Jacqueline W. Daykin, Costas S. Iliopoulos, and William F. Smyth. Parallel RAM algorithms for factorizing words. \it Theor. Comput. Sci., 127(1):53-67, 1994.
[12] Olivier Delgrange and Eric Rivals. STAR: an algorithm to search for tandem approximate repeats. \it Bioinformatics, 20(16):2812-2820, 2004.
[13] Jean-Pierre Duval. Factorizing words over an ordered alphabet. \it J. Algorithms, 4(4):363- 381, 1983.
[14] Frantisek Franek, A. S. M. Sohidull Islam, Mohammad Sohel Rahman, and William F. Smyth. Algorithms to compute the Lyndon array. In \it Proceedings of the Prague Stringology \it Conference 2016, Prague, Czech Republic, August 29-31, 2016, pages 172-184, 2016.
[15] Harold Fredricksen and James Maiorana. Necklaces of beads in k colors and k-ary de Bruijn sequences. \it Discrete Mathematics, 23(3):207-210, 1978.
[16] Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. \it SIAM J. Comput., 13(2):338-355, 1984.
[17] Christophe Hohlweg and Christophe Reutenauer. Lyndon words, permutations and trees. \it Theor. Comput. Sci., 307(1):173-178, 2003. doi:10.1016/S0304-3975(03)00099-9.
[18] Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster Lyndon factorization algorithms for SLP and LZ78 compressed text. \it Theor. Comput. \it Sci., 656:215-224, 2016.
[19] M. Lothaire. \it Combinatorics on Words. Addison-Wesley, 1983.
[20] :10
[21] R. C. Lyndon. On Burnside’s problem. \it Transactions of the American Mathematical Society, 77:202-215, 1954.
[22] Marcin Mucha. Lyndon words and short superstrings. In \it Proc. SODA’13, pages 958-972, 2013.
[23] Yuto Nakashima, Takuya Takagi, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. On reverse engineering the Lyndon tree. In \it Proceedings of the Prague Stringology Confer- \it ence 2017, Prague, Czech Republic, August 28-30, 2017, pages 108-117, 2017.
[24] Shoshana Neuburger and Dina Sokol. Succinct 2D dictionary matching. \it Algorithmica, pages 1-23, 2012. 10.1007/s00453-012-9615-9.
[25] Xavier Provençal. Minimal non-convex words. \it Theor. Comput. Sci., 412(27):3002-3009, 2011.
[26] E. Ukkonen. On-line construction of suffix trees. \it Algorithmica, 14(3):249-260, 1995.
[27] P. Weiner. Linear pattern-matching algorithms. In \it Proc. of 14
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.