Quasi-Linear-Time Algorithm for Longest Common Circular Factor

Mai Alzamel; Maxime Crochemore; Costas S. Iliopoulos; Tomasz Kociumaka; Jakub Radoszewski; Wojciech Rytter; Juliusz  Straszynski; Tomasz Walen; Wiktor  Zuba

doi:10.4230/LIPIcs.CPM.2019.25

Quasi-Linear-Time Algorithm for Longest Common Circular Factor

Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Citations (Scopus)

96 Downloads (Pure)

Abstract

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 ⁴ n) time using O(nlog ² n) space.

Original language	English
Title of host publication	30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019
Editors	Nadia Pisanti, Solon P. Pissis
Publisher	LIPIcs
Chapter	25
Pages	25:1–25:14
Volume	128
ISBN (Electronic)	9783959771030
DOIs	https://doi.org/10.4230/LIPIcs.CPM.2019.25
Publication status	Published - 6 Jun 2019

Keywords

Circular pattern matching
Internal pattern matching
Intersection of hyperrectangles
Longest common factor

Access to Document

10.4230/LIPIcs.CPM.2019.25Licence: CC BY

Quasi-Linear-Time Algorithm_ALZAMEL_Publishedonline6June2019_GOLD VoR (CC BY)Final published version, 616 KBLicence: CC BY

Cite this

Alzamel, M., Crochemore, M., Iliopoulos, C. S., Kociumaka, T., Radoszewski, J., Rytter, W., Straszynski, J., Walen, T., & Zuba, W. (2019). Quasi-Linear-Time Algorithm for Longest Common Circular Factor. In N. Pisanti, & S. P. Pissis (Eds.), 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019 (Vol. 128, pp. 25:1–25:14). LIPIcs. https://doi.org/10.4230/LIPIcs.CPM.2019.25

@inproceedings{3e0d268a3b974a5ab48030d3cc3ac92e,

title = "Quasi-Linear-Time Algorithm for Longest Common Circular Factor",

abstract = "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. ",

keywords = "Circular pattern matching, Internal pattern matching, Intersection of hyperrectangles, Longest common factor",

author = "Mai Alzamel and Maxime Crochemore and Iliopoulos, {Costas S.} and Tomasz Kociumaka and Jakub Radoszewski and Wojciech Rytter and Juliusz Straszynski and Tomasz Walen and Wiktor Zuba",

year = "2019",

month = jun,

day = "6",

doi = "10.4230/LIPIcs.CPM.2019.25",

language = "English",

volume = "128",

pages = "25:1–25:14",

editor = "Nadia Pisanti and Pissis, {Solon P.}",

booktitle = "30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019",

publisher = "LIPIcs",

}

Quasi-Linear-Time Algorithm for Longest Common Circular Factor. / Alzamel, Mai ; Crochemore, Maxime ; Iliopoulos, Costas S. et al.
30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019. ed. / Nadia Pisanti; Solon P. Pissis. Vol. 128 LIPIcs, 2019. p. 25:1–25:14.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Quasi-Linear-Time Algorithm for Longest Common Circular Factor

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this