# 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
.
In Press.

*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_.

Publication Type: | Journal Article |
---|---|

Murdoch Affiliation: | School of Engineering and Information Technology |

Publisher: | Elsevier BV |

Copyright: | © 2018 |

URI: | http://researchrepository.murdoch.edu.au/id/eprint/42476 |

Item Control Page |