×

zbMATH — the first resource for mathematics

Computing longest palindromic substring after single-character or block-wise edits. (English) Zbl 07310533
Summary: Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of the longest palindromic substrings (LPSs) of a given string \(T\) of length \(n\) can be computed in \(O(n)\) time by Manacher’s algorithm [12]. In this paper, we consider the problem of finding the LPS after the string is edited. We present an algorithm that uses \(O(n)\) time and space for preprocessing, and answers the length of the LPSs in \(O(\log(\min \{\sigma, \log n\}))\) time after a 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 LPSs in \(O(\ell + \log \log n)\) time, after an existing substring in \(T\) is replaced by a string of arbitrary length \(\ell\).
MSC:
68Q Theory of computing
Software:
EERTREE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Funakoshi, M.; Nakashima, Y.; Inenaga, S.; Bannai, H.; Takeda, M., Longest substring palindrome after edit, (CPM 2018 (2018)), 12:1-12:14 · Zbl 07286738
[2] Funakoshi, M.; Nakashima, Y.; Inenaga, S.; Bannai, H.; Takeda, M., Faster queries for longest substring palindrome after block edit, (30th Annual Symposium on Combinatorial Pattern Matching. 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, June 18-20, 2019, Pisa, Italy (2019)), 27:1-27:13
[3] Apostolico, A.; Breslauer, D.; Galil, Z., Parallel detection of all palindromes in a string, Theor. Comput. Sci., 141, 163-173 (1995) · Zbl 0873.68039
[4] Matsubara, W.; Inenaga, S.; Ishino, A.; Shinohara, A.; Nakamura, T.; Hashimoto, K., Efficient algorithms to compute compressed longest common substrings and compressed palindromes, Theor. Comput. Sci., 410, 8-10, 900-913 (2009) · Zbl 1162.68038
[5] Groult, R.; Prieur, É.; Richomme, G., Counting distinct palindromes in a word in linear time, Inf. Process. Lett., 110, 20, 908-912 (2010) · Zbl 1234.68329
[6] Kosolobov, D.; Rubinchik, M.; Shur, A. M., Finding distinct subpalindromes online, (PSC 2013 (2013)), 63-69
[7] Porto, A. H.L.; Barbosa, V. C., Finding approximate palindromes in strings, Pattern Recognit., 35, 2581-2591 (2002) · Zbl 1006.68910
[8] Kolpakov, R.; Kucherov, G., Searching for gapped palindromes, Theor. Comput. Sci., 410, 51, 5365-5373 (2009) · Zbl 1187.68367
[9] Narisada Diptarama, S.; Narisawa, K.; Inenaga, S.; Shinohara, A., Computing longest single-arm-gapped palindromes in a string, (SOFSEM 2017 (2017)), 375-386 · Zbl 1444.68310
[10] Gawrychowski, P.; Inenaga, T. I.S.; Köppl, D.; Manea, F., Tighter bounds and optimal algorithms for all maximal α-gapped repeats and palindromes - finding all maximal α-gapped repeats and palindromes in optimal worst case time on integer alphabets, Theory Comput. Syst., 62, 1, 162-191 (2018) · Zbl 1386.68120
[11] Adamczyk, M.; Alzamel, M.; Charalampopoulos, P.; Radoszewski, J., Palindromic decompositions with gaps and errors, Int. J. Found. Comput. Sci., 29, 8, 1311-1329 (2018) · Zbl 1415.68268
[12] Manacher, G., A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string, J. ACM, 22, 346-351 (1975) · Zbl 0305.68027
[13] Weiner, P., Linear pattern matching algorithms, (14th Annual Symposium on Switching and Automata Theory (1973)), 1-11
[14] Gusfield, D., Algorithms on Strings, Trees, and Sequences (1997), Cambridge University Press · Zbl 0934.68103
[15] Rubinchik, M.; Shur, A. M., EERTREE: an efficient data structure for processing palindromes in strings, (Combinatorial Algorithms - 26th International Workshop. Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers (2015)), 321-333 · Zbl 06562495
[16] Berenbrink, P.; Ergün, F.; Mallmann-Trenn, F.; Azer, E. S., Palindrome recognition in the streaming model, (STACS 2014 (2014)), 149-161 · Zbl 1359.68330
[17] Gawrychowski, P.; Merkurev, O.; Shur, A. M.; Uznanski, P., Tight tradeoffs for real-time approximation of longest palindromes in streams, (CPM 2016 (2016)), 18:1-18:13 · Zbl 1380.68475
[18] Amir, A.; Charalampopoulos, P.; Iliopoulos, C. S.; Pissis, S. P.; Radoszewski, J., Longest common factor after one edit operation, (SPIRE 2017 (2017)), 14-26
[19] Abedin, P.; Hooshmand, S.; Ganguly, A.; Thankachan, S. V., The heaviest induced ancestors problem revisited, (Annual Symposium on Combinatorial Pattern Matching. Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2-4, 2018 - Qingdao, China (2018)), 20:1-20:13 · Zbl 07286746
[20] Urabe, Y.; Nakashima, Y.; Inenaga, S.; Bannai, H.; Takeda, M., Longest Lyndon substring after edit, (CPM 2018 (2018)), 19:1-19:10 · Zbl 07286745
[21] Amir, A.; Charalampopoulos, P.; Pissis, S. P.; Radoszewski, J., Longest common substring made fully dynamic, (27th Annual European Symposium on Algorithms. 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany (2019)), 6:1-6:17
[22] Amir, A.; Boneh, I., Dynamic palindrome detection (2019), CoRR
[23] Amir, A.; Boneh, I.; Charalampopoulos, P.; Kondratovsky, E., Repetition detection in a dynamic string, (Bender, M. A.; Svensson, O.; Herman, G., ESA. ESA, LIPIcs, vol. 144 (2019)), 5:1-5:18
[24] Charalampopoulos, P.; Gawrychowski, P.; Pokorski, K., Dynamic longest common substring in polylogarithmic time, (47th International Colloquium on Automata, Languages, and Programming. 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference) (2020)), 27:1-27:19
[25] Harel, D.; Tarjan, R. E., Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 2, 338-355 (1984) · Zbl 0535.68022
[26] Schieber, B.; Vishkin, U., On finding lowest common ancestors: simplification and parallelization, SIAM J. Comput., 17, 6, 1253-1262 (1988) · Zbl 0669.68049
[27] Bender, M. A.; Farach-Colton, M., The LCA problem revisited, (LATIN 2000 (2000)), 88-94 · Zbl 0959.68133
[28] Farach-Colton, M.; Ferragina, P.; Muthukrishnan, S., On the sorting-complexity of suffix tree construction, J. ACM, 47, 6, 987-1011 (2000) · Zbl 1094.68694
[29] Gąsieniec, L.; Karpinski, M.; Plandowski, W.; Rytter, W., Efficient algorithms for Lempel-Ziv encoding, (Proc. 5th Scandinavian Workshop on Algorithm Theory. Proc. 5th Scandinavian Workshop on Algorithm Theory, SWAT1996. Proc. 5th Scandinavian Workshop on Algorithm Theory. Proc. 5th Scandinavian Workshop on Algorithm Theory, SWAT1996, LNCS, vol. 1097 (1996), Springer), 392-403
[30] Manber, U.; Myers, G., Suffix arrays: a new method for on-line string searches, SIAM J. Comput., 22, 5, 935-948 (1993) · Zbl 0784.68027
[31] Berkman, O.; Vishkin, U., Finding level-ancestors in trees, J. Comput. Syst. Sci., 48, 2, 214-230 (1994) · Zbl 0806.68027
[32] Bender, M. A.; Farach-Colton, M., The level ancestor problem simplified, Theor. Comput. Sci., 321, 1, 5-12 (2004) · Zbl 1068.68047
[33] Cole, R.; Hariharan, R., Dynamic LCA queries on trees, SIAM J. Comput., 34, 4, 894-923 (2005) · Zbl 1075.68019
[34] Ukkonen, E., On-line construction of suffix trees, Algorithmica, 14, 3, 249-260 (1995) · Zbl 0831.68027
[35] Matsubara, T. I.W.; Shimohira, K.; Inenaga, S.; Bannai, H.; Takeda, M.; Narisawa, K.; Shinohara, A., Detecting regularities on grammar-compressed strings, Inf. Comput., 240, 74-89 (2015) · Zbl 1312.68238
[36] Rubinchik, M.; Shur, A. M., Palindromic k-factorization in pure linear time, (45th International Symposium on Mathematical Foundations of Computer Science. 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic. 45th International Symposium on Mathematical Foundations of Computer Science. 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, LIPIcs, vol. 170 (2020), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 81:1-81:14
[37] Kosolobov, D.; Rubinchik, M.; Shur, A. M., Pal k is linear recognizable online, (SOFSEM 2015: Theory and Practice of Computer Science - 41st International Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM 2015: Theory and Practice of Computer Science - 41st International Conference on Current Trends in Theory and Practice of Computer Science, Pec pod Sněžkou, Czech Republic, January 24-29, 2015. Proceedings (2015)), 289-301 · Zbl 1432.68228
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.