Quasi-Linear-Time Algorithm for Longest Common Circular Factor

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

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

6 Citations (Scopus)
77 Downloads (Pure)

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.

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

Keywords

  • Circular pattern matching
  • Internal pattern matching
  • Intersection of hyperrectangles
  • Longest common factor

Fingerprint

Dive into the research topics of 'Quasi-Linear-Time Algorithm for Longest Common Circular Factor'. Together they form a unique fingerprint.

Cite this