# 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
##### Keywords:
combinatorics on words; counting algorithms
Full Text:
##### References:
  Badkobeh, G; Crochemore, M, Computing maximal-exponent factors in an overlap-free word, J. Comput. Syst Sci., 82, 477-487, (2016) · Zbl 1333.68303  Bannai, H., Tomohiro, I., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The runs theorem. arXiv:1406.0263 (2014) · Zbl 1375.68093  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  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  Crochemore, M; Tischler, G, Computing longest previous non-overlapping factors, Inf. Process. Lett., 111, 291-295, (2011) · Zbl 1260.68488  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  Crochemore, M., Kolpakov, R., Kucherov, G.: Optimal Bounds for Computing $$α$$-Gapped Repeats Proc. LATA, pp 245-255 (2016) · Zbl 1443.68137  Dumitran, M., Manea, F.: Longest Gapped Repeats and Palindromes Proc. MFCS, volume 9234 of LNCS, pp 205-217 (2015) · Zbl 06482736  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  Gawrychowski, P., Manea, F.: Longest $$α$$-Gapped Repeat and Palindrome Proc. FCT, volume 9210 of LNCS, pp 27-40 (2015) · Zbl 1433.68631  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  Gawrychowski, P., Manea, F., Nowotka, D.: Testing Generalised Freeness of Words Proc. STACS, volume 25 of LIPIcs, pp 337-349 (2014) · Zbl 1359.68336  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  Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997) · Zbl 0934.68103  Kärkkäinen, J; Sanders, P; Burkhardt, S, Linear work suffix array construction, J. ACM, 53, 918-936, (2006) · Zbl 1326.68111  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)  Kolpakov, R., Kucherov, G.: Finding Repeats with Fixed Gap Proc. SPIRE, pp 162-168 (2000) · Zbl 1260.68488  Kolpakov, R; Kucherov, G, Searching for gapped palindromes, Theor. Comput. Sci., 410, 5365-5373, (2009) · Zbl 1187.68367  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  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  Ruzic, M.: Making deterministic signatures quickly. ACM Transactions on Algorithms 5 (3) (2009) · Zbl 1298.68117  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.