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