×

zbMATH — the first resource for mathematics

Longest substring palindrome after edit. (English) Zbl 07286738
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 12, 14 p. (2018).
Summary: It is known that the length of the longest substring palindromes (LSPals) of a given string \(T\) of length \(n\) can be computed in \(O(n)\) time by G. Manacher’s algrithm [J. Assoc. Comput. Mach. 22, 346–351 (1975; Zbl 0305.68027)]. In this paper, we consider the problem of finding the LSPal after the string is edited. We present an algorithm that uses \(O(n)\) time and space for preprocessing, and answers the length of the LSPals in \(O(\log(\min \{\sigma,\log n\}))\) time after single character substitution, insertion, or deletion, where \(\sigma\) denotes the number of distinct characters appearing in \(T\). We also propose an algorithm that uses \(O(n)\) time and space for preprocessing, and answers the length of the LSPals in \(O(\ell+\log n)\) time, after an existing substring in \(T\) is replaced by a string of arbitrary length \(\ell\).
For the entire collection see [Zbl 1390.68025].

MSC:
68W32 Algorithms on strings
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 SPIRE 2017, pages 14-26, 2017.
[2] Alberto Apostolico, Dany Breslauer, and Zvi Galil. Parallel detection of all palindromes in a string. \it Theoretical Computer Science, 141:163-173, 1995.
[3] Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In \it LATIN \it 2000, pages 88-94, 2000.
[4] Richard Cole and Ramesh Hariharan. Dynamic LCA queries on trees. \it SIAM J. Comput., 34(4):894-923, 2005.
[5] Martin Farach-Colton, Paolo Ferragina, and S. Muthukrishnan. On the sorting-complexity of suffix tree construction. \it J. ACM, 47(6):987-1011, 2000.
[6] Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea. Tighter bounds and optimal algorithms for all maximal \it α-gapped repeats and palindromes - finding all maximal \it α-gapped repeats and palindromes in optimal worst case time on integer alphabets. \it Theory Comput. Syst., 62(1):162-191, 2018.
[7] Leszek G¸asieniec, Marek Karpinski, Wojciech Plandowski, and Wojciech Rytter. Efficient algorithms for Lempel-Ziv encoding. In \it Proc. 5th Scandinavian Workshop on Algorithm \it Theory (SWAT1996), volume 1097 of \it LNCS, pages 392-403. Springer, 1996.
[8] Richard Groult, Élise Prieur, and Gwénaël Richomme. Counting distinct palindromes in a word in linear time. \it Inf. Process. Lett., 110(20):908-912, 2010.
[9] Dan Gusfield. \it Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.
[10] Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. \it SIAM J. Comput., 13(2):338-355, 1984.
[11] Roman Kolpakov and Gregory Kucherov. Searching for gapped palindromes. \it Theor. Com- \it put. Sci., 410(51):5365-5373, 2009.
[12] Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur. Finding distinct subpalindromes online. In \it Proceedings of the Prague Stringology Conference 2013, Prague, Czech \it Republic, September 2-4, 2013, pages 63-69, 2013.
[13] Glenn Manacher. A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string. \it Journal of the ACM, 22:346-351, 1975.
[14] W. Matsubara, S. Inenaga, A. Ishino, A. Shinohara, T. Nakamura, and K. Hashimoto. Efficient algorithms to compute compressed longest common substrings and compressed palindromes. \it Theor. Comput. Sci., 410(8-10):900-913, 2009.
[15] Shintaro Narisada, Diptarama, Kazuyuki Narisawa, Shunsuke Inenaga, and Ayumi Shinohara. Computing longest single-arm-gapped palindromes in a string. In \it SOFSEM 2017, pages 375-386, 2017.
[16] Alexandre H. L. Porto and Valmir C. Barbosa. Finding approximate palindromes in strings. \it Pattern Recognition, 35:2581-2591, 2002.
[17] Baruch Schieber and Uzi Vishkin. On finding lowest common ancestors: Simplification and parallelization. \it SIAM J. Comput., 17(6):1253-1262, 1988.
[18] E. Ukkonen. On-line construction of suffix trees. \it Algorithmica, 14(3):249-260, 1995.
[19] Peter Weiner. Linear pattern matching algorithms. In \it 14th Annual Symposium on Switching \it and Automata Theory, pages 1-11, 1973.
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.