Quasi-Linear-Time Algorithm for Longest Common Circular Factor

2019/01/31 by Alzamel, Mai, Crochemore, Maxime, Iliopoulos, Costas S. +6
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1901.11305

Abstract

We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings S and T of length 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⁵ n) time.

Related

• Algorithms for Longest Common Abelian Factors
• Linear-Time Algorithm for Long LCF with k Mismatches
• Longest Property-Preserved Common Factor
• Solving Cyclic Longest Common Subsequence in Quadratic Time
• An O(n²) Algorithm for Computing Longest Common Cyclic Subsequence