TY - JOUR
T1 - Off-line and on-line algorithms for closed string factorization
AU - Alzamel, Mai
AU - Iliopoulos, Costas S.
AU - Smyth, W.F.
AU - Sung, Wing-Kin
PY - 2018/10/30
Y1 - 2018/10/30
N2 - 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′.
AB - 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′.
KW - Closed string
KW - On-line
KW - Minimum factorization
U2 - 10.1016/j.tcs.2018.10.033
DO - 10.1016/j.tcs.2018.10.033
M3 - Article
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -
TY - CHAP
T1 - Degenerate String Comparison and Applications
AU - Alzamel, Mai
AU - Ayad, Lorraine A. K.
AU - Bernardini, Giulia
AU - Grossi, Roberto
AU - Iliopoulos, Costas S.
AU - Pisanti, Nadia
AU - Pissis, Solon P.
AU - Rosone, Giovanna
PY - 2018
Y1 - 2018
U2 - 10.4230/LIPIcs.WABI.2018.21
DO - 10.4230/LIPIcs.WABI.2018.21
M3 - Conference paper
SN - 9783959770828
VL - 113
T3 - Leibniz International Proceedings in Informatics (LIPIcs)
SP - 21:1-21:14
BT - 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)
A2 - Parida, Laxmi
A2 - Ukkonen, Esko
PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY - Dagstuhl, Germany
ER -
TY - CHAP
T1 - How to Answer a Small Batch of RMQs or LCA Queries in Practice
AU - Alzamel, Mai
AU - Charalampopoulos, Panagiotis
AU - Iliopoulos, Costas S.
AU - Pissis, Solon P.
PY - 2018
Y1 - 2018
U2 - 10.1007/978-3-319-78825-8_28
DO - 10.1007/978-3-319-78825-8_28
M3 - Conference paper
VL - 10765
T3 - Lecture Notes in Computer Science
SP - 343
EP - 355
BT - Combinatorial Algorithms
A2 - Brankovic, Ljiljana
A2 - Ryan, Joe
A2 - Smyth, William F.
PB - Springer International Publishing
CY - Cham
ER -