×

zbMATH — the first resource for mathematics

Computing longest single-arm-gapped palindromes in a string. (English) Zbl 1444.68310
Steffen, Bernhard (ed.) et al., SOFSEM 2017: theory and practice of computer science. 43rd international conference on current trends in theory and practice of computer science, Limerick, Ireland, January 16–20, 2017, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10139, 375-386 (2017).
Summary: We introduce new types of approximate palindromes called single-arm-gapped palindromes (SAGPs). A SAGP contains a gap in either its left or right arm, which is in the form of either \(wguc u^R w^R\) or \(wuc u^Rgw^R\), where \(w\) and \(u\) are non-empty strings, \(w^R\) and \(u^R\) are their reversed strings respectively, \(g\) is a gap, and \(c\) is either a single character or the empty string. We classify SAGPs into two groups: those which have \(ucu^R\) as a maximal palindrome (type-1), and the others (type-2). We propose several algorithms to compute all type-1 SAGPs with longest arms occurring in a given string using suffix arrays, and them a linear-time algorithm based on suffix trees. We also show how to compute type-2 SAGPs with longest arms in linear time. We perform some preliminary experiments to evaluate practical performances of the proposed methods.
For the entire collection see [Zbl 1355.68020].

MSC:
68W32 Algorithms on strings
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apostolico, A., Breslauer, D., Galil, Z.: Parallel detection of all palindromes in a string. Theor. Comput. Sci. 141(1&2), 163–173 (1995) · Zbl 0873.68039 · doi:10.1016/0304-3975(94)00083-U
[2] Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000). doi: 10.1007/10719839_9 · Zbl 0959.68133 · doi:10.1007/10719839_9
[3] Droubay, X., Pirillo, G.: Palindromes and sturmian words. Theor. Comput. Sci. 223(1–2), 73–85 (1999) · Zbl 0930.68116 · doi:10.1016/S0304-3975(97)00188-6
[4] van Emde Boas, P.: Preserving order in a forest in less than logarithmic time. In: FOCS, pp. 75–84 (1975) · doi:10.1109/SFCS.1975.26
[5] 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 · doi:10.1145/355541.355547
[6] Fujishige, Y., Nakamura, M., Inenaga, S., Bannai, H., Takeda, M.: Finding gapped palindromes online. In: Mäkinen, V., Puglisi, S.J., Salmela, L. (eds.) IWOCA 2016. LNCS, vol. 9843, pp. 191–202. Springer, Heidelberg (2016). doi: 10.1007/978-3-319-44543-4_15 · Zbl 06631021 · doi:10.1007/978-3-319-44543-4_15
[7] Gawrychowski, P., Tomohiro, I., Inenaga, S., Köppl, D., Manea, F.: Efficiently finding all maximal \[ \alpha \] -gapped repeats. In: STACS 2016, pp. 39:1–39:14 (2016) · Zbl 1380.68320
[8] Glen, A., Justin, J., Widmer, S., Zamboni, L.Q.: Palindromic richness. Eur. J. Comb. 30(2), 510–531 (2009) · Zbl 1169.68040 · doi:10.1016/j.ejc.2008.04.006
[9] Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, New York (1997) · Zbl 0934.68103 · doi:10.1017/CBO9780511574931
[10] Hsu, P.H., Chen, K.Y., Chao, K.M.: Finding all approximate gapped palindromes. Int. J. Found. Comput. Sci. 21(6), 925–939 (2010) · Zbl 1209.68399 · doi:10.1142/S0129054110007647
[11] Kärkkäinen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918–936 (2006) · Zbl 1326.68111 · doi:10.1145/1217856.1217858
[12] Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A. (ed.) CPM 2001. LNCS, vol. 2089, pp. 181–192. Springer, Heidelberg (2001). doi: 10.1007/3-540-48194-X_17 · Zbl 0990.68639 · doi:10.1007/3-540-48194-X_17
[13] Kolpakov, R., Kucherov, G.: Searching for gapped palindromes. Theor. Comput. Sci. 410(51), 5365–5373 (2009) · Zbl 1187.68367 · doi:10.1016/j.tcs.2009.09.013
[14] Manacher, G.K.: A new linear-time on-line algorithm for finding the smallest initial palindrome of a string. J. ACM 22(3), 346–351 (1975) · Zbl 0305.68027 · doi:10.1145/321892.321896
[15] Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935–948 (1993) · Zbl 0784.68027 · doi:10.1137/0222058
[16] Shi, Y.Z., Wang, F.H., Wu, Y.Y., Tan, Z.J.: A coarse-grained model with implicit salt for RNAs: predicting 3D structure, stability and salt effect. J. Chem. Phys. 141(10), 105102 (2014) · doi:10.1063/1.4894752
[17] Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, pp. 1–11 (1973) · doi:10.1109/SWAT.1973.13
[18] Westbrook, J.: Fast incremental planarity testing. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 342–353. Springer, Heidelberg (1992). doi: 10.1007/3-540-55719-9_86 · doi:10.1007/3-540-55719-9_86
[19] Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \[ \varTheta (N) \] . Information Processing Letters 17, 81–84 (1983) · Zbl 0509.68106 · doi:10.1016/0020-0190(83)90075-3
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.