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.
|Title of host publication||30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019|
|Editors||Nadia Pisanti, Solon P. Pissis|
|Publication status||Published - 6 Jun 2019|
- Circular pattern matching
- Internal pattern matching
- Intersection of hyperrectangles
- Longest common factor