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 -
TY - CHAP
T1 - A Brief Overview of Dead-Zone Pattern Matching Algorithms
AU - Alshammary, Miznah Hizam
AU - Alzamel, Mai Abdulaziz M
AU - Iliopoulos, Costas
AU - Watson, Richard T.
AU - Watson, Bruce
PY - 2019/5/15
Y1 - 2019/5/15
N2 - Within the last decades, the dead-zone algorithms have emerged as being highly performant on certain types of data. Such algorithms solve the keyword exact matching problem over strings, though extensions to trees and two-dimensional data have also been devised. In this short paper, we give an overview of such algorithms.
AB - Within the last decades, the dead-zone algorithms have emerged as being highly performant on certain types of data. Such algorithms solve the keyword exact matching problem over strings, though extensions to trees and two-dimensional data have also been devised. In this short paper, we give an overview of such algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85065921354&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19909-8_18
DO - 10.1007/978-3-030-19909-8_18
M3 - Conference paper
SN - 9783030199081
VL - 560
T3 - IFIP Advances in Information and Communication Technology
SP - 208
EP - 218
BT - Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops
A2 - Pimenidis, Elias
A2 - Iliadis, Lazaros
A2 - Maglogiannis, Ilias
A2 - MacIntyre, John
PB - Springer
ER -
TY - CHAP
T1 - On the Cyclic Regularities of Strings
AU - Ajala, Oluwole Ifeanyi
AU - Alshammary, Miznah Hizam
AU - Alzamel, Mai Abdulaziz M
AU - Gao, Jia
AU - Iliopoulos, Costas
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Watson, Bruce
PY - 2019/5/15
Y1 - 2019/5/15
N2 - Regularities in strings are often related to periods and covers, which have extensively been studied, and algorithms for their efficient computation have broad application. In this paper we concentrate on computing cyclic regularities of strings, in particular, we propose several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers.
AB - Regularities in strings are often related to periods and covers, which have extensively been studied, and algorithms for their efficient computation have broad application. In this paper we concentrate on computing cyclic regularities of strings, in particular, we propose several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers.
KW - Covers
KW - Cyclic regularities
KW - Periods
UR - http://www.scopus.com/inward/record.url?scp=85065922538&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19909-8_19
DO - 10.1007/978-3-030-19909-8_19
M3 - Conference paper
SN - 9783030199081
VL - 560
T3 - IFIP Advances in Information and Communication Technology
SP - 219
EP - 224
BT - Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops
A2 - Maglogiannis, Ilias
A2 - Iliadis, Lazaros
A2 - MacIntyre, John
A2 - Pimenidis, Elias
PB - Springer
ER -