Quasi-Linear-Time Algorithm for Longest Common Circular Factor

01/31/2019
by   Mai Alzamel, et al.
0

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 ^5 n) time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset