King's College London

Research portal

Quasi-Linear-Time Algorithm for Longest Common Circular Factor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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
PublisherLIPIcs
Chapter25
Pages25:1–25:14
Volume128
ISBN (Electronic)9783959771030
DOIs
Publication statusPublished - 6 Jun 2019

Documents

King's Authors

Abstract

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.

View graph of relations

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