Quasi-linear-time algorithm for a longest common circular factor

We consider 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 is a factor of T. This new similarity measure is an extension of the classic Longest Common Factor. We show an algorithm solving the LCCF problem in O ( n log 3 n log ( r + 2 ) ) time, where r ≤ n is the length of the output, using O ( n ) space. A naive algorithm works in Ω(n 2) time, and no O ( n polylog n ) -time solution was known prior to our work. Our result constitutes yet another application of string synchronizing sets of Kempa and Kociumaka (STOC 2019). Compared to the preliminary version published at CPM 2019, we significantly simplified the algorithm and improved the space complexity from O ( n log 2 n ) to O ( n ). We achieved that with new algorithmic insights into a certain geometric intersection problem, solved by suitably decomposing intervals.

Authors

• Mai Alzamel
• Maxime Crochemore
• Costas S. Iliopoulos
• Tomasz Kociumaka
• Jakub Radoszewski
• Wojciech Rytter
• Juliusz Straszyński
• Tomasz Waleń
• Wiktor Zuba

Keywords

• Longest common factor
• Cyclic shift (rotation)
• String synchronizing set