Catalog Home Page

Off-line and on-line algorithms for closed string factorization

Alzamel, M., Iliopoulos, C.S., Smyth, W.F. and Sung, W-K (2018) Off-line and on-line algorithms for closed string factorization. Theoretical Computer Science, 792 . pp. 12-19.

[img]
PDF - Authors' Version
Embargoed until October 2020.

Link to Published Version: https://doi.org/10.1016/j.tcs.2018.10.033
*Subscription may be required

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 ofX, X2 the longest closed prefix ofX with prefixX1 removed, and so on. In this paper we present an O(log n) 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(n log2 n)-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(Llog n) 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_.

Item Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2018 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/42476
Item Control Page Item Control Page