Quasi-linear-time algorithm for a longest common circular factor
We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings S and T of length at most n, we are to compute the longest factor of S whose cyclic shift occurs as a factor of T. It is a new similarity measure, an extension of the classic Longest Common Factor. We show how to solve the LCCF problem in O(n log^4 n) time using O(n log^2 n) space.
Authors
- Mai Alzamel (ORCID: https://orcid.org/0000-0002-0862-7452)
- Costas S. Iliopoulos (ORCID: https://orcid.org/0000-0003-3909-0077)
- Tomasz Waleń (ORCID: https://orcid.org/0000-0002-7369-3309)
- Wojciech Rytter (ORCID: https://orcid.org/0000-0002-9162-6724)
- Maxime Crochemore (ORCID: https://orcid.org/0000-0003-1087-1419)
- Jakub Radoszewski (ORCID: https://orcid.org/0000-0002-0067-6401)
- Wiktor Zuba (ORCID: https://orcid.org/0000-0002-1988-3507)
- Tomasz Kociumaka (ORCID: https://orcid.org/0000-0002-2477-1702)
- Juliusz Straszyński (ORCID: https://orcid.org/0000-0003-2207-0053)
Institutions
- King's College London (GB)
- Université Gustave Eiffel (FR)
- University of Warsaw (PL)
Publication Details
- Journal
- Theoretical Computer Science
- Published
- 2026-04-07
- DOI
- https://doi.org/10.1016/j.tcs.2026.115955
- Citations
- 1
- Primary Topic
- Algorithms and Data Compression
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- European Commission
- Fundacja na rzecz Nauki Polskiej
- King Saud University
- Israel Science Foundation
- Narodowe Centrum Nauki
- European Regional Development Fund