Abstract
A k-antipower (for \(k \ge 2\)) is a concatenation of k pairwise distinct words of the same length. The study of antipower factors of a word was initiated by Fici et al. (ICALP 2016) and first algorithms for computing antipower factors were presented by Badkobeh et al. (Inf. Process. Lett., 2018). We address two open problems posed by Badkobeh et al. Our main results are algorithms for counting and reporting factors of a word which are k-antipowers. They work in \(\mathcal {O}(nk \log k)\) time and \(\mathcal {O}(nk \log k\,+\,C)\) time, respectively, where C is the number of reported factors. For \(k=o(\sqrt{n/\log n})\), this improves the time complexity of \(\mathcal {O}(n^2/k)\) of the solution by Badkobeh et al. Our main algorithmic tools are runs and gapped repeats. We also present an improved data structure that checks, for a given factor of a word and an integer k, if the factor is a k-antipower.
T. Kociumaka and W. Rytter—Supported by the Polish National Science Center, grant no 214/13/B/ST6/00770.
J. Radoszewski and J. Straszyński—Supported by the “Algorithms for text processing with errors and uncertainties” project carried out within the HOMING program of the Foundation for Polish Science co-financed by the European Union under the European Regional Development Fund.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Badkobeh, G., Fici, G., Puglisi, S.J.: Algorithms for anti-powers in strings. Inf. Process. Lett. 137, 57–60 (2018). https://doi.org/10.1016/j.ipl.2018.05.003
Bannai, H., I, T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The “runs” theorem. SIAM J. Comput. 46(5), 1501–1514 (2017). https://doi.org/10.1137/15M1011032
Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75–94 (2005). https://doi.org/10.1016/j.jalgor.2005.08.001
Bentley, J.L.: Algorithms for Klee’s rectangle problems. Unpublished notes, Computer Science Department, Carnegie Mellon University (1977)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Crochemore, M., Kolpakov, R., Kucherov, G.: Optimal bounds for computing \(\alpha \)-gapped repeats. In: Dediu, A.-H., Janoušek, J., Martín-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 245–255. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30000-9_19
Fici, G., Restivo, A., Silva, M., Zamboni, L.Q.: Anti-powers in infinite words. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) Automata, Languages and Programming, ICALP 2016. LIPIcs, vol. 55, pp. 124:1–124:9. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230/LIPIcs.ICALP.2016.124
Fici, G., Restivo, A., Silva, M., Zamboni, L.Q.: Anti-powers in infinite words. J. Comb. Theory Ser. A 157, 109–119 (2018). https://doi.org/10.1016/j.jcta.2018.02.009
Gawrychowski, P., I, T., Inenaga, S., Köppl, D., Manea, F.: 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. Theory Comput. Syst. 62(1), 162–191 (2018). https://doi.org/10.1007/s00224-017-9794-5
Kociumaka, T., Radoszewski, J., Rytter, W., Straszyński, J., Waleń, T., Zuba, W.: Efficient representation and counting of antipower factors in words. arXiv preprint arXiv:1812.08101 (2018)
Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, pp. 596–604. IEEE Computer Society (1999). https://doi.org/10.1109/SFFCS.1999.814634
Kolpakov, R., Podolskiy, M., Posypkin, M., Khrapov, N.: Searching of gapped repeats and subrepetitions in a word. J. Discrete Algorithms 46–47, 1–15 (2017). https://doi.org/10.1016/j.jda.2017.10.004
Rubinchik, M., Shur, A.M.: Counting palindromes in substrings. In: Fici, G., Sciortino, M., Venturini, R. (eds.) SPIRE 2017. LNCS, vol. 10508, pp. 290–303. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67428-5_25
Tanimura, Y., Fujishige, Y., I, T., Inenaga, S., Bannai, H., Takeda, M.: A faster algorithm for computing maximal \(\alpha \)-gapped repeats in a string. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 124–136. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23826-5_13
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Kociumaka, T., Radoszewski, J., Rytter, W., Straszyński, J., Waleń, T., Zuba, W. (2019). Efficient Representation and Counting of Antipower Factors in Words. In: Martín-Vide, C., Okhotin, A., Shapira, D. (eds) Language and Automata Theory and Applications. LATA 2019. Lecture Notes in Computer Science(), vol 11417. Springer, Cham. https://doi.org/10.1007/978-3-030-13435-8_31
Download citation
DOI: https://doi.org/10.1007/978-3-030-13435-8_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-13434-1
Online ISBN: 978-3-030-13435-8
eBook Packages: Computer ScienceComputer Science (R0)