@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", }
@article{494a1cbddd84401e94ac745ec58e638e, title = "Faster algorithms for 1-mappability of a sequence", abstract = "In the k-mappability problem, we are given a string x of length n and integers m and k, and we are asked to count, for each length-m factor y of x, the number of other factors of length m of x that are at Hamming distance at most k from y. We focus here on the version of the problem where k=1. There exists an algorithm to solve this problem for k=1 requiring time O(mnlogn/loglogn) using space O(n). Here we present two new algorithms that require worst-case time O(mn) and O(nlognloglogn), respectively, and space O(n), thus greatly improving the previous result. Moreover, we present another algorithm that requires average-case time and space O(n) for integer alphabets of size σ if m=Ω(log σn). Notably, we show that this algorithm is generalizable for arbitrary k, requiring average-case time O(kn) and space O(n) if m=Ω(klog σn), assuming that the letters are independent and uniformly distributed random variables. Finally, we provide an experimental evaluation of our average-case algorithm demonstrating its competitiveness to the state-of-the-art implementation. ", keywords = "Algorithms on strings, Hamming distance, Sequence mappability", author = "Mai Alzamel and Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Pissis, {Solon P.} and Jakub Radoszewski and Wing-Kin Sung", year = "2019", month = may, day = "23", doi = "10.1016/j.tcs.2019.04.026", language = "English", journal = "Theoretical Computer Science", issn = "0304-3975", publisher = "Elsevier", }
@inbook{61e2e43714f941739c99b1b1f3642418, title = "A Brief Overview of Dead-Zone Pattern Matching Algorithms", abstract = "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.", author = "Alshammary, {Miznah Hizam} and Alzamel, {Mai Abdulaziz M} and Costas Iliopoulos and Watson, {Richard T.} and Bruce Watson", year = "2019", month = may, day = "15", doi = "10.1007/978-3-030-19909-8_18", language = "English", isbn = "9783030199081", volume = "560", series = "IFIP Advances in Information and Communication Technology", publisher = "Springer", pages = "208--218", editor = "Elias Pimenidis and Lazaros Iliadis and Ilias Maglogiannis and John MacIntyre", booktitle = "Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops", }
@inbook{11a5ee11428646a9ac241349e1d75394, title = "On the Cyclic Regularities of Strings", abstract = "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.", keywords = "Covers, Cyclic regularities, Periods", author = "Ajala, {Oluwole Ifeanyi} and Alshammary, {Miznah Hizam} and Alzamel, {Mai Abdulaziz M} and Jia Gao and Costas Iliopoulos and Jakub Radoszewski and Wojciech Rytter and Bruce Watson", year = "2019", month = may, day = "15", doi = "10.1007/978-3-030-19909-8_19", language = "English", isbn = "9783030199081", volume = "560", series = "IFIP Advances in Information and Communication Technology", publisher = "Springer", pages = "219--224", editor = "Ilias Maglogiannis and Lazaros Iliadis and John MacIntyre and Elias Pimenidis", booktitle = "Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops", }