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

M. Alzamel; C.S. Iliopoulos; W.F. Smyth; W-K Sung

doi:10.1016/j.tcs.2018.10.033

Back

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

Journal article

Open access

Peer reviewed

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

M. Alzamel, C.S. Iliopoulos, W.F. Smyth and W-K Sung

Theoretical Computer Science, Vol.792, pp.12-19

2018

DOI: https://doi.org/10.1016/j.tcs.2018.10.033

Files and links (2)

pdf

Off-line and on-line algorithms for closed string factorization.pdfDownload View

Author’s Version Open Access

url

Link to Published Version *Subscription may be requiredView

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

Details

Title: Off-line and on-line algorithms for closed string factorization
Authors/Creators: M. Alzamel (Author/Creator) - King Saud University
C.S. Iliopoulos (Author/Creator) - King's College London
W.F. Smyth (Author/Creator) - McMaster University
W-K Sung (Author/Creator) - National University of Singapore
Publication Details: Theoretical Computer Science, Vol.792, pp.12-19
Publisher: Elsevier BV
Identifiers: 991005542756007891
Murdoch Affiliation: School of Engineering and Information Technology
Language: English
Resource Type: Journal article

Metrics

89 File views/ downloads

52 Record Views

3 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1103 Efficient Algorithms
Web Of Science research areas: Computer Science, Theory & Methods
ESI research areas: Computer Science