TY - GEN
T1 - Quasi-Linear-Time Algorithm for Longest Common Circular Factor
AU - Alzamel, Mai
AU - Crochemore, Maxime
AU - Iliopoulos, Costas S.
AU - Kociumaka, Tomasz
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Straszynski, Juliusz
AU - Walen, Tomasz
AU - Zuba, Wiktor
PY - 2019/6/6
Y1 - 2019/6/6
N2 - 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.
AB - 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.
KW - Circular pattern matching
KW - Internal pattern matching
KW - Intersection of hyperrectangles
KW - Longest common factor
UR - http://www.scopus.com/inward/record.url?scp=85068064362&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2019.25
DO - 10.4230/LIPIcs.CPM.2019.25
M3 - Conference contribution
VL - 128
SP - 25:1–25:14
BT - 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019
A2 - Pisanti, Nadia
A2 - Pissis, Solon P.
PB - LIPIcs
ER -