@article{a57e0f5cc48746efb0094195583ee140, title = "Off-line and on-line algorithms for closed string factorization", abstract = "A string X=X[1..n], n>1, is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X; for n=1, every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al.[2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X=X1X2⋯Xk, where X1 is the longest closed prefix of X, X2 the longest closed prefix of X with prefix X1 removed, and so on. In this paper we present an O(logn) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X. We first describe an off-line O(nlog2n)-time algorithm to compute MCF(X), then we present an on-line algorithm for the same problem. In fact, we show that MCF(X) can be computed in O(Llogn) time from MCF(X′), where X′=X[1..n−1], and L is the largest integer such that the suffix X[n−L+1..n] is a substring of X′.", keywords = "Closed string, On-line, Minimum factorization", author = "Mai Alzamel and Iliopoulos, {Costas S.} and W.F. Smyth and Wing-Kin Sung", year = "2018", month = oct, day = "30", doi = "10.1016/j.tcs.2018.10.033", language = "English", journal = "Theoretical Computer Science", issn = "0304-3975", publisher = "Elsevier", }
@inbook{5528908b64004249819dac50dcda2c59, title = "Degenerate String Comparison and Applications", author = "Mai Alzamel and Ayad, {Lorraine A. K.} and Giulia Bernardini and Roberto Grossi and Iliopoulos, {Costas S.} and Nadia Pisanti and Pissis, {Solon P.} and Giovanna Rosone", year = "2018", doi = "10.4230/LIPIcs.WABI.2018.21", language = "English", isbn = "9783959770828", volume = "113", series = "Leibniz International Proceedings in Informatics (LIPIcs)", publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik", pages = "21:1--21:14", editor = "Laxmi Parida and Esko Ukkonen", booktitle = "18th International Workshop on Algorithms in Bioinformatics (WABI 2018)", }
@inbook{c21be3e905d942cb93ca15089fcc4e47, title = "How to Answer a Small Batch of RMQs or LCA Queries in Practice", author = "Mai Alzamel and Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Pissis, {Solon P.}", year = "2018", doi = "10.1007/978-3-319-78825-8_28", language = "English", volume = "10765", series = "Lecture Notes in Computer Science", publisher = "Springer International Publishing", pages = "343--355", editor = "Ljiljana Brankovic and Joe Ryan and Smyth, {William F.}", booktitle = "Combinatorial Algorithms", }