Efficient Algorithms to Compute Closed Substrings

Abstract A closed string u is either of length one or contains a non-empty border that occurs only as a prefix and as a suffix in u and nowhere else within u. In this paper, we present fast \(\mathcal {O}(n\log n)\) time algorithms to compute all \(\mathcal {O}(n^2)\) closed substrings by introducing a compact representation for all closed substrings of a string w[1..n], using only \(\mathcal {O}(n \log n)\) space. These simple and space-efficient algorithms also compute maximal closed strings. Furthermore, we compare the performance of these algorithms and identify classes of strings where each performs best. Finally, we show that the exact number of maximal closed substrings in a Fibonacci word \( f_n \), for \(n \ge 5\), is \(\approx \left( 1 + \frac{1}{\phi ^2}\right) F_n \approx 1.382 F_n\), where \( \phi \) is the golden ratio and \(F_n\) = \(|f_n|\). Data Availability \(\bullet \) Bill Smyth’s String Repository - https://www.cas.mcmaster.ca/~bill/strings \(\bullet \) Pizza&Chili Text Collection - https://pizzachili.dcc.uchile.cl/texts.html \(\bullet \) Digits of \(\pi \) - https://calculat.io/storage/pi/100m.zip \(\bullet \) Human Chromosome 1 - https://www.ncbi.nlm.nih.gov/nuccore/NC_000001.11 Code Availability References Fici, G.: A classification of Trapezoidal words. In: Ambrož, P., Holub, Masáková, Z. (eds.) Proceedings of the 8th International Conference WORDS 2011, Prague, Czech Republic, 12–16 September 2011. Electronic Proceedings in Theoretical Computer Science, vol. 63, pp. 129–137. Open Publishing Association, Online (2011). https://doi.org/10.4204/EPTCS.63.18 Badkobeh, G., Bannai, H., Goto, K., I, T., Iliopoulos, C.S., Inenaga, S., Puglisi, S.J., Sugimoto, S.: Closed factorization. In: Holub, J., Zdařek, J. (eds.) Proceedings of PSC 2014, pp. 162–168. Czech Technical University in Prague, Czech Republic (2014). https://www.stringology.org/papers/PSC2014.pdf Bannai, H., Inenaga, S., Kociumaka, T., Lefebvre, A., Radoszewski, J., Rytter, W., Sugimoto, S., Waleń, T.: Efficient algorithms for longest closed factor array. In: String Processing and Information Retrieval, pp. 95–102. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23826-5_10 Badkobeh, G., Bannai, H., Goto, K., I, T., Iliopoulos, C.S., Inenaga, S., Puglisi, S.J., Sugimoto, S.: Closed factorization. Discr. Appl. Math. 212, 23–29 (2016). https://doi.org/10.1016/j.dam.2016.04.009 Alamro, H., Alzamel, M., Iliopoulos, C.S., Pissis, S.P., Watts, S., Sung, W.-K.: Efficient identification of k-closed strings. In: Boracchi, G., Iliadis, L., Jayne, C., Likas, A. (eds.) Engineering Applications of Neural Networks, pp. 583–595. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-65172-9_49 Jahannia, M., Mohammad-Noori, M., Rampersad, N., Stipulanti, M.: Closed Ziv-Lempel factorization of the m-bonacci words. Theoret. Comput. Sci. 918, 32–47 (2022). https://doi.org/10.1016/j.tcs.2022.03.019 Parshina, O., Zamboni, L.Q.: Open and closed factors in Arnoux-Rauzy words. Adv. Appl. Math. 107, 22–31 (2019). https://doi.org/10.1016/j.aam.2019.02.007 Badkobeh, G., Fici, G., Lipták, Z.: On the number of closed factors in a word. In: Dediu, A.-H., Formenti, E., Martín-Vide, C., Truthe, B. (eds.) Language and Automata Theory and Applications, pp. 381–390. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15579-1_29 Parshina, O., Puzynina, S.: Finite and infinite closed-rich words. Theoret. Comput. Sci. 984, 114315 (2024). https://doi.org/10.1016/j.tcs.2023.114315 Mieno, T., Takahashi, S., Seto, K., Horiyama, T.: Online and offline algorithms for counting distinct closed factors via sliding suffix trees. In: Královič, R., Kůrková, V. (eds.) SOFSEM 2025: Theory and Practice of Computer Science, pp. 172–183. Springer, Cham (2025). https://doi.org/10.1007/978-3-031-82697-9_13 Badkobeh, G., De Luca, A., Fici, G., Puglisi, S.J.: Maximal closed substrings. In: Arroyuelo, D., Poblete, B. (eds.) String Processing and Information Retrieval, pp. 16–23. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-20643-6_2 Badkobeh, G., De Luca, A., Fici, G., Puglisi, S.J.: Finding maximal closed substrings. Theoret. Comput. Sci. 1060, 115628 (2026). https://doi.org/10.1016/j.tcs.2025.115628 Kosolobov, D.: Closed Repeats (2024). https://doi.org/10.48550/arXiv.2410.00209 Jain, S.K., Mhaskar, N., Badkobeh, G., Radoszewski, J., Tonellotto, N.: Efficient computation of closed substrings. In: Baeza-Yates, R. (ed.) String Processing and Information Retrieval, pp. 172–187. Springer, Cham (2026). https://doi.org/10.1007/978-3-032-05228-5_15 Mhaskar, N., Smyth, W.F.: String covering: A survey. Fund. Inform. 190(1), 17–45 (2023). https://doi.org/10.3233/FI-222164 Crochemore, M.: An optimal algorithm for computing the repetitions in a word. Inf. Process. Lett. 12(5), 244–250 (1981). https://doi.org/10.1016/0020-0190(81)90024-7 Kociumaka, T., Pissis, S.P., Radoszewski, J., Rytter, W., Waleń, T.: Fast algorithm for partial covers in words. Algorithmica 73(1), 217–233 (2015). https://doi.org/10.1007/s00453-014-9915-3 Brodal, G.S., Pedersen, C.N.S.: Finding maximal quasiperiodicities in strings. In: Giancarlo, R., Sankoff, D. (eds.) Combinatorial Pattern Matching, pp. 397–411. Springer, Berlin, Heidelberg (2000). https://doi.org/10.1007/3-540-45123-4_33 Brown, M.R., Tarjan, R.E.: A fast merging algorithm. J. ACM 26(2), 211–226 (1979). https://doi.org/10.1145/322123.322127 Smyth, B.: Computing Patterns in Strings. ACM Press Bks. Pearson Addison-Wesley, Harlow, Essex, England (2003). https://books.google.ca/books?id=iKR0EewiCu4C Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory (swat 1973), pp. 1–11. (1973). https://doi.org/10.1109/SWAT.1973.13 Brodal, G.S., Lyngsø, R.B., Pedersen, C.N.S., Stoye, J.: Finding maximal pairs with bounded gap. In: Crochemore, M., Paterson, M. (eds.) Combinatorial Pattern Matching, pp. 134–149. Springer, Berlin, Heidelberg (1999) Bucci, M., De Luca, A., Fici, G.: Enumeration and structure of Trapezoidal words. Theoret. Comput. Sci. 468, 12–22 (2013). https://doi.org/10.1016/j.tcs.2012.11.007 De Luca, A., Fici, G., Zamboni, L.Q.: The sequence of open and closed prefixes of a Sturmian word. Adv. Appl. Math. 90, 27–45 (2017). https://doi.org/10.1016/j.aam.2017.04.007 Kolpakov, R., Kucherov, G.: On maximal repetitions in words. In: Ciobanu, G., Păun, G. (eds.) Fundamentals of Computation Theory, pp. 374–385. Springer, Berlin, Heidelberg (1999). https://doi.org/10.1007/3-540-48321-7_31 Yamane, K., Nakashima, Y., Seto, K., Horiyama, T.: Maximal \(\alpha \)-gapped repeats in a Fibonacci string. In: Královič, R., Kůrková, V. (eds.) SOFSEM 2025: Theory and Practice of Computer Science, pp. 337–350. Springer, Cham (2025). https://doi.org/10.1007/978-3-031-82697-9_25 Moore, D., Smyth, W.F.: An optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 50(5), 239–246 (1994). https://doi.org/10.1016/0020-0190(94)00045-X Grebnov, I.: libsais: A library for linear time suffix array, longest common prefix array and Burrows-Wheeler transform construction based on induced sorting algorithm. GitHub repository. Version 2.10.2, last updated June 12, 2025 (2021–2025). https://github.com/IlyaGrebnov/libsais Kärkkäinen, J., Manzini, G., Puglisi, S.J.: Permuted longest-common-prefix array. In: Kucherov, G., Ukkonen, E. (eds.) Combinatorial Pattern Matching, pp. 181–192. Springer, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02441-2_17 Nong, G., Zhang, S., Chan, W.H.: Two efficient algorithms for linear time suffix array construction. IEEE Trans. Comput. 60(10), 1471–1484 (2011). https://doi.org/10.1109/TC.2010.188 Timoshevskaya, N., Feng, W.: Sais-opt: On the characterization and optimization of the sa-is algorithm for suffix array construction. In: 2014 IEEE 4th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS), pp. 1–6 (2014). https://doi.org/10.1109/ICCABS.2014.6863917 Xie, J.Y., Nong, G., Lao, B., Xu, W.: Scalable suffix sorting on a multicore machine. IEEE Trans. Comput. 69(9), 1364–1375 (2020). https://doi.org/10.1109/TC.2020.2972546 Czajka, P., Radoszewski, J.: Experimental evaluation of algorithms for computing quasiperiods. Theoret. Comput. Sci. 854, 17–29 (2021). https://doi.org/10.1016/j.tcs.2020.11.033 Franek, F., Smyth, W.F., Xiao, X.: A note on Crochemore’s repetitions algorithm: A fast, space-efficient approach. In: Proceedings of PSC 2002, pp. 36–43. Department of Computer Science and Engineering, Czech Technical University in Prague, Czech Republic (2002). https://www.stringology.org/event/2002/p5.html Acknowledgements We thank Simon J. Puglisi for introducing us to the MCS problem using \(\textsf{SA}\) and \(\textsf{LCP}\), which led to Theorem 5. We are grateful to the reviewers for their valuable feedback. Funding Neerja Mhaskar was funded by Natural Sciences & Engineering Research Council of Canada [Grant Number RGPIN-2024-06915]. Author information Authors and Affiliations Contributions KJ, S : Initial conceptualization, Writing - original draft preparation, figures (including graphs), experiments and code implementation and string generation M.N : Funding acquisition & Supervision KJ, S & M.N : Methodology, Formal analysis and investigation, Writing - review and editing Corresponding author Ethics declarations Competing interests The authors declare no competing interests. Consent for publication The authors consent to publish the paper. Additional information Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Rights and permissions Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law. About this article Cite this article Jain, S.K., Mhaskar, N. Efficient Algorithms to Compute Closed Substrings. Theory Comput Syst 70, 48 (2026). https://doi.org/10.1007/s00224-026-10290-x Received: Accepted: Published: Version of record: DOI: https://doi.org/10.1007/s00224-026-10290-x