King's College London

Research portal

Quasi-Linear-Time Algorithm for Longest Common Circular Factor

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba

Original languageEnglish
Title of host publication30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019
EditorsNadia Pisanti, Solon P. Pissis
ISBN (Electronic)9783959771030
Accepted/In press2019
Published6 Jun 2019


King's Authors


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(nlog 4 n) time using O(nlog 2 n) space.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454