2026-07-21T12:58:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10496 2024-03-06T10:45:53Z ddc:004 open_access

Quasi-Linear-Time Algorithm for Longest Common Circular Factor Alzamel, Mai Crochemore, Maxime Iliopoulos, Costas S. Kociumaka, Tomasz Radoszewski, Jakub Rytter, Wojciech Straszyński, Juliusz Waleń, Tomasz Zuba, Wiktor longest common factor circular pattern matching internal pattern matching intersection of hyperrectangles 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(n log^4 n) time using O(n log^2 n) space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mai Alzamel and Maxime Crochemore and Costas S. Iliopoulos and Tomasz Kociumaka and Jakub Radoszewski and Wojciech Rytter and Juliusz Straszyński and Tomasz Waleń and Wiktor Zuba 2019 Is Part Of LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2019.25 urn:nbn:de:0030-drops-104961 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.25 eng https://creativecommons.org/licenses/by/3.0/legalcode