Research output: Contribution to journal › Article

Mai Alzamel, Costas S. Iliopoulos, W.F. Smyth, Wing-Kin Sung

Original language | English |
---|---|

Journal | Theoretical Computer Science |

Early online date | 30 Oct 2018 |

DOIs | |

Publication status | E-pub ahead of print - 30 Oct 2018 |

**Off-line and on-line algorithms_ALZAMEL_Firstonline30October2018_GREEN AAM (CC BY-NC-ND)**Off_line_and_on_line_algorithms_ALZAMEL_Firstonline30October2018_GREEN_AAM_CC_BY_NC_ND_.pdf, 304 KB, application/pdf

30/10/2019

Accepted author manuscript

CC BY-NC-ND

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′.

No data available

King's College London - Homepage

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454