×

zbMATH — the first resource for mathematics

Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets. (English) Zbl 1386.68120
Summary: An \(\alpha\)-gapped repeat \((\alpha\geq 1)\) in a word \(w\) is a factor \(uvu\) of \(w\) such that \(| uv|\leq\alpha| u|\); the two occurrences of \(u\) are called arms of this \(\alpha\)-gapped repeat. An \(\alpha\)-gapped repeat is called maximal if its arms cannot be extended simultaneously with the same character to the right nor to the left. We show that the number of all maximal \(\alpha\)-gapped repeats occurring in words of length \(n\) is upper bounded by \(18\alpha n\). In the case of \(\alpha\)-gapped palindromes, i.e., factors \(uvu^{\top}\) with \(| uv|\leq\alpha| u|\), we show that the number of all maximal \(\alpha\)-gapped palindromes occurring in words of length \(n\) is upper bounded by \(28\alpha n+7n\). Both upper bounds allow us to construct algorithms finding all maximal \(\alpha\)-gapped repeats and/or all maximal \(\alpha\)-gapped palindromes of a word of length \(n\) on an integer alphabet of size \(n^{\mathcal{O}(1)}\) in \(\mathcal O(\alpha n)\) time. The presented running times are optimal since there are words that have \(\Theta(\alpha n)\) maximal \(\alpha\)-gapped repeats/palindromes.

MSC:
68R15 Combinatorics on words
68W32 Algorithms on strings
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Badkobeh, G; Crochemore, M, Computing maximal-exponent factors in an overlap-free word, J. Comput. Syst Sci., 82, 477-487, (2016) · Zbl 1333.68303
[2] Bannai, H., Tomohiro, I., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The runs theorem. arXiv:1406.0263 (2014) · Zbl 1375.68093
[3] Brodal, G.S., Lyngsø, R. B., Pedersen, C. N. S., Stoye, J.: Finding maximal pairs with bounded gap Proc. CPM, volume 1645 of LNCS, pp 134-149 (1999) · Zbl 1063.68614
[4] Crochemore, M; Rytter, W, Usefulness of the karp-Miller-rosenberg algorithm in parallel computations on strings and arrays, Theor. Comput. Sci., 88, 59-82, (1991) · Zbl 0737.68037
[5] Crochemore, M; Tischler, G, Computing longest previous non-overlapping factors, Inf. Process. Lett., 111, 291-295, (2011) · Zbl 1260.68488
[6] Crochemore, M., Iliopoulos, C. S., Kubica, M., Rytter, W., Walen, T.: Efficient Algorithms for Two Extensions of LPF table: The Power of Suffix Arrays Proc. SOFSEM, volume 5901 of LNCS, pp 296-307 (2010) · Zbl 1274.68670
[7] Crochemore, M., Kolpakov, R., Kucherov, G.: Optimal Bounds for Computing \(α\)-Gapped Repeats Proc. LATA, pp 245-255 (2016) · Zbl 1443.68137
[8] Dumitran, M., Manea, F.: Longest Gapped Repeats and Palindromes Proc. MFCS, volume 9234 of LNCS, pp 205-217 (2015) · Zbl 06482736
[9] Fischer, J; Heun, V, Space efficient preprocessing schemes for range minimum queries on static arrays, SIAM J. Comput., 40, 465-492, (2011) · Zbl 1222.05024
[10] Gawrychowski, P., Manea, F.: Longest \(α\)-Gapped Repeat and Palindrome Proc. FCT, volume 9210 of LNCS, pp 27-40 (2015) · Zbl 1433.68631
[11] Gawrychowski, P., Manea, F., Mercas, R., Nowotka, D., Tiseanu, C.: Finding Pseudo-repetitions Proc. STACS, volume 20 of LIPIcs, pp 257-268 (2013) · Zbl 1354.68215
[12] Gawrychowski, P., Manea, F., Nowotka, D.: Testing Generalised Freeness of Words Proc. STACS, volume 25 of LIPIcs, pp 337-349 (2014) · Zbl 1359.68336
[13] Gawrychowski, P., Tomohiro, I., Inenaga, S., Köppl, D., Manea, F.: Efficiently finding all maximal \(α\)-gapped repeats Proc. STACS, volume 47 of LIPIcs, pp 39:1-39:14 (2016) · Zbl 1380.68320
[14] Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997) · Zbl 0934.68103
[15] Kärkkäinen, J; Sanders, P; Burkhardt, S, Linear work suffix array construction, J. ACM, 53, 918-936, (2006) · Zbl 1326.68111
[16] Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T.: Efficient Data Structures for the Factor Periodicity Problem Proc. SPIRE, volume 7608 of LNCS, pp 284-294 (2012)
[17] Kolpakov, R., Kucherov, G.: Finding Repeats with Fixed Gap Proc. SPIRE, pp 162-168 (2000) · Zbl 1260.68488
[18] Kolpakov, R; Kucherov, G, Searching for gapped palindromes, Theor. Comput. Sci., 410, 5365-5373, (2009) · Zbl 1187.68367
[19] Kolpakov, R., Podolskiy, M., Posypkin, M., Khrapov, N.: Searching of Gapped Repeats and Subrepetitions in a Word Proc. CPM, volume 8486 of LNCS, pp 212-221 (2014) · Zbl 1407.68382
[20] 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
[21] Ruzic, M.: Making deterministic signatures quickly. ACM Transactions on Algorithms 5 (3) (2009) · Zbl 1298.68117
[22] Tanimura, Y., Fujishige, Y., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: A faster algorithm for computing maximal \(α\)-gapped repeats in a string Proc. SPIRE, volume 9309 of LNCS, pp 124-136 (2015)
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.