Search

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

A factor u of a string y is a cover of y if every letter of y lies within some occurrence of u in y; thus every cover u is also a border—both prefix and suffix—of y. If u is a cover of a superstring of y then u is a seed of y. Covers and seeds are two formalisations of quasiperiodicity, and there exist linear-time algorithms for computing all the covers and seeds of y. A string y covered by u thus generalises the idea of a repetition; that is, a string composed of exact concatenations of u. Even though a string is coverable somewhat more frequently than it is a repetition, still a string that can be covered by a single u is rare. As a result, seeking to find a more generally applicable and descriptive notion of cover, many articles were written on the computation of a minimum k-cover of y; that is, the minimum cardinality set of strings of length k that collectively cover y. Unfortunately, this computation turns out to be NP-hard. Therefore, in this article, we propose new, simple, easily-computed, and widely applicable notions of string covering that provide an intuitive and useful characterisation of a string: the enhanced cover; the enhanced left cover; and the enhanced left seed.

The study of approximately periodic strings is relevant to diverse applications such as molecular biology, data compression, and computer-assisted music analysis. Here we study different forms of approximate periodicity under a variety of distance functions. We consider three related problems, for two of which we derive polynomial-time algorithms; we then show that the third problem is NP-complete.

A (finite) Fibonacci stringFn is defined as follows: F0 = b, F1 = a; for every integer n ⩾ 2, Fn = Fn − 1Fn − 2. For n ⩾ 1, the length of Fn is denoted by . The infinite Fibonacci stringF is the string which contains every Fn, n ⩾ 1, as a prefix. Apart from their general theoretical importance, Fibonacci strings are often cited as worst-case examples for algorithms which compute all the repetitions or all the “Abelian squares” in a given string. In this paper we provide a characterization of all the squares in F, hence in every prefix Fn; this characterization naturally gives rise to a algorithm which specifies all the squares of Fn in an appropriate encoding. This encoding is made possible by the fact that the squares of Fn occur consecutively, in “runs”, the number of which is . By contrast, the known general algorithms for the computation of the repetitions in an arbitrary string require time (and produce outputs) when applied to a Fibonacci string Fn.

An O(logn log log n) CRCW PRAM algorithm using O(n/log n) processors for computing the unique Lyndon factorization of a word of length n over an unbounded alphabet is presented; this improves the bounds given by Apostolico and Crochemore (1989). Moreover, in the case of fixed alphabets the CRCW PRAM algorithm is optimal (linear cost), requiring O(log n) units of time.

An O(log n) time CRCW PRAM algorithm for computing the least lexicographic rotation of a circular string (of length n) over a fixed alphabet is presented here. The logarithmic running time is achieved by using processors and its space complexity is linear. A second algorithm for unbounded alphabets requires O(log n log log n) units of time, also using processors.