A Lyndon word is a word that is lexicographically smaller than all of its non-trivial rotations (e.g. ananas is a Lyndon word; banana is not a Lyndon word due to its smaller rotation abanan). The Lyndon forest (or equivalently Lyndon table) identifies maximal Lyndon factors of a word, and is of great combinatoric interest, e.g. when finding maximal repetitions in words. While optimal linear time algorithms for computing the Lyndon forest are known, none of them work in an online manner. We present algorithms that compute the Lyndon forest of a word in a reverse online manner, processing the input word from back to front. We assume a general ordered alphabet, i.e. the only elementary operations on symbols are comparisons of the form less-equal-greater. We start with a naive algorithm and show that, despite its quadratic worst-case behaviour, it already takes expected linear time on words drawn uniformly at random. We then introduce a much more sophisticated algorithm that takes linear time in the worst case. It borrows some ideas from the offline algorithm by Bille et al. (ICALP 2020), combined with new techniques that are necessary for the reverse online setting. While the back-to-front approach for this computation is rather natural (see Franek and Liut, PSC 2019), the steps required to achieve linear time are surprisingly intricate. We envision that our algorithm will be useful for the online computation of maximal repetitions in words.

We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings $S$ and $T$ of length $n$, we are to compute the longest factor of $S$ whose cyclic shift occurs as a factor of $T$. It is a new similarity measure, an extension of the classic Longest Common Factor. We show how to solve the LCCF problem in $O(n \log^5 n)$ time.

In the Longest Common Factor with k Mismatches (LCF_k) problem, we are given two strings X and Y of total length n, and we are asked to find a pair of maximal-length factors, one of X and the other of Y, such that their Hamming distance is at most k. Thankachan et al. [Thankachan et al. 2016] show that this problem can be solved in O(n log^k n) time and O(n) space for constant k. We consider the LCF_k(l) problem in which we assume that the sought factors have length at least l. We use difference covers to reduce the LCF_k(l) problem with l=Omega(log^{2k+2}n) to a task involving m=O(n/log^{k+1}n) synchronized factors. The latter can be solved in O(m log^{k+1}m) time, which results in a linear-time algorithm for LCF_k(l) with l=Omega(log^{2k+2}n). In general, our solution to the LCF_k(l) problem for arbitrary l takes O(n + n log^{k+1} n/sqrt{l}) time.

Computing genetic evolution distances among a set of taxa dominates the running time of many phylogenetic inference methods. Most of genetic evolution distance definitions rely, even if indirectly, on computing the pairwise Hamming distance among sequences or profiles. We propose here an average-case linear-time algorithm to compute pairwise Hamming distances among a set of taxa under a given Hamming distance threshold. This article includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a well known phylogenetic inference method.

Given a set $\mathcal{D}$ ofqdocuments, the Longest Common Substring (LCS) problem asks, for any integer 2 ⩽k⩽q, the longest substring that appears inkdocuments. LCS is a well-studied problem having a wide range of applications in Bioinformatics: from microarrays to DNA sequences alignments and analysis. This problem has been solved by Hui (2000International Journal of Computer Science and Engineering1573–76) by using a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with the use of suffix trees. In this article, we present a simple method for solving the LCS problem by using suffix trees (STs) and classical union-find data structures. In turn, we show how this simple algorithm can be adapted in order to work with other space efficient data structures such as the enhanced suffix arrays (ESA) and the compressed suffix tree.

LZ77-based compression schemes compress the input text by replacing factors in the text with an encoded reference to a previous occurrence formed by the couple (length, offset). For a given factor, the smallest is the offset, the smallest is the resulting compression ratio. This is optimally achieved by using the rightmost occurrence of a factor in the previous text. Given a cost function, for instance the minimum number of bits used to represent an integer, we define the Rightmost Equal-Cost Position (REP) problem as the problem of finding one of the occurrences of a factor whose cost is equal to the cost of the rightmost one. We present the Multi-Layer Suffix Tree data structure that, for a text of length n, at any time i, it provides REP(LPF) in constant time, where LPF is the longest previous factor, i.e. the greedy phrase, a reference to the list of REP({set of prefixes of LPF}) in constant time and REP(p) in time O(|p| log log n) for any given pattern p.

We study the class of periodic-finite-type (PFT) shift spaces, which can be used to model time-varying constrained codes used in digital magnetic recording systems. A PFT shift is determined by a finite list of periodically forbidden words. We show that the class of PFT shifts properly contains all finite-type (FT) shifts, and the class of almost finite-type (AFT) shifts properly contains all PFT shifts. We establish several basic properties of PFT shift spaces of a given period$T$, and provide a characterization of such a shift in terms of properties of its Shannon cover (i.e., its unique minimal, deterministic, irreducible graph presentation). We present an algorithm that, given the Shannon cover${\cal G}$of an irreducible sofic shift$X$, decides whether or not$X$is PFT in time that is quadratic in the number of states of${\cal G}$. From any periodic irreducible presentation of a given period, we define a periodic forbidden list, unique up to conjugacy (a circular permutation) for that period, that satisfies certain minimality properties. We show that an irreducible sofic shift is PFT if and only if the list corresponding to its Shannon cover${\cal G}$and its period is finite. Finally, we discuss methods for computing the capacity of a PFT shift from a periodic forbidden list, either by construction of a corresponding graph or in a combinatorial manner directly from the list itself.

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both the cases, we develop efficient solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.

The Prefix table of a string reports for each position the maximal length of its prefixes starting here. The Prefix table and its dual Suffix table are basic tools used in the design of the most efficient string-matching and pattern extraction algorithms. These tables can be computed in linear time independently of the alphabet size. We give an algorithmic characterisation of a Prefix table (it can be adapted to a Suffix table). Namely, the algorithm tests if an integer table of size $n$ is the Prefix table of some word and, if successful, it constructs the lexicographically smallest string having it as a Prefix table. We show that the alphabet of the string can be bounded to $\log_2 n$ letters. The overall algorithm runs in $O(n)$ time.

We give a space-efficient simple algorithm for computing the Lempel-Ziv factorization of a string. For a string of length n over an integer alphabet, it runs in O(n) time independently of alphabet size and uses o(n) additional space.

The cornerstone of any algorithm computing all repetitions in a string of length $n$ in ${mathcal O(n)$ time is the fact that the number of runs (or maximal repetitions) is ${mathcal O(n)$. We give a simple proof of this result. As a consequence of our approach, the stronger result concerning the linearity of the sum of exponents of all runs follows easily.

The Range Next Value problem (Problem RNV) is a recent interesting variant of the range search problems, where the query is for the immediate next (or equal) value of a given number within a given interval of an array. Problem RNV was introduced and studied very recently by Crochemore et. al [Finding Patterns In Given Intervals, MFCS 2007]. In this paper, we present improved algorithms for Problem RNV. We also show how this problem can be used to achieve optimal query time for a number of interesting variants of the classic pattern matching problems.

We design an algorithm that minimizes irreducible deterministic local automata by a sequence of state mergings. Two states can be merged if they have exactly the same outputs. The running time of the algorithm is O(min(m(n-r+1), m log n)), where m is the number of edges, n the number of states of the automaton, and r the number of states of the minimized automaton. In particular, the algorithm is linear when the automaton is already minimal and contrary to Hopcroft's minimization algorithm that has a O (kn log n) running time in this case, where k is the size of the alphabet, and that applies only to complete automata. (Note that kn ges m.) While Hopcroft's algorithm relies on a "negative strategy", starting from a partition with a single class of all states, and partitioning classes when it is discovered that two states cannot belong to the same class, our algorithm relies on a "positive strategy", starting from the trivial partition for which each class is a singleton. Two classes are then merged when their leaders have the same outputs. The algorithm applies to irreducible deterministic local automata, where all states are considered both initial and final. These automata, also called covers, recognize symbolic dynamical shifts of finite type. They serve to present a large class of constrained channels, the class of finite memory systems, used for channel coding purposes. The algorithm also applies to irreducible deterministic automata that are left-closing and have a synchronizing word. These automata present shifts that are called almost of finite type. Almost-of-finite-type shifts make a meaningful class of shifts, intermediate between finite type shifts and sofic shifts.

Motif inference represents one of the most important areas of research in computational biology, and one of its oldest ones. Despite this, the problem remains very much open in the sense that no existing definition is fully satisfying, either in formal terms, or in relation to the biological questions that involve finding such motifs. Two main types of motifs have been considered in the literature: matrices (of letter frequency per position in the motif) and patterns. There is no conclusive evidence in favor of either, and recent work has attempted to integrate the two types into a single model. In this paper, we address the formal issue in relation to motifs as patterns. This is essential to get at a better understanding of motifs in general. In particular, we consider a promising idea that was recently proposed, which attempted to avoid the combinatorial explosion in the number of motifs by means of a generator set for the motifs. Instead of exhibiting a complete list of motifs satisfying some input constraints, what is produced is a basis of such motifs from which all the other ones can be generated. We study the computational cost of determining such a basis of repeated motifs with wild cards in a sequence. We give new upper and lower bounds on such a cost, introducing a notion of basis that is provably contained in (and, thus, smaller) than previously defined ones. Our basis can be computed in less time and space, and is still able to generate the same set of motifs. We also prove that the number of motifs in all bases defined so far grows exponentially with the quorum, that is, with the minimal number of times a motif must appear in a sequence, something unnoticed in previous work. We show that there is no hope to efficiently compute such bases unless the quorum is fixed.

We give a polynomial-time construction of the set of sequences that satisfy a finite-memory constraint defined by a finite list of forbidden blocks, with a specified set of bit positions unconstrained. Such a construction can be used to build modulation/error-correction codes (ECC codes) like the ones defined by the Immink-Wijngaarden scheme in which certain bit positions are reserved for ECC parity. We give a linear-time construction of a finite-state presentation of a constrained system defined by a periodic list of forbidden blocks. These systems, called periodic-finite-type (PFT) systems, were introduced by Moision and Siegel. Finally, we present a linear-time algorithm for constructing the minimal periodic forbidden blocks of a finite sequence for a given period.

Given two strings of size n over a constant alphabet, the classical algorithm for computing the similarity between two sequences [D. Sankoff and J. B. Kruskal, eds., {Time Warps, String Edits, and Macromolecules}; Addison-Wesley, Reading, MA, 1983; T. F. Smith and M. S. Waterman, { J.\ Molec.\ Biol., 147 (1981), pp. 195-197] uses a dynamic programming matrix and compares the two strings in O(n 2 ) time. We address the challenge of computing the similarity of two strings in subquadratic time for metrics which use a scoring matrix of unrestricted weights. Our algorithm applies to both {local} and {global} similarity computations. The speed-up is achieved by dividing the dynamic programming matrix into variable sized blocks, as induced by Lempel-Ziv parsing of both strings, and utilizing the inherent periodic nature of both strings. This leads to an $O(n^2 / \log n)$, algorithm for an input of constant alphabet size. For most texts, the time complexity is actually $O(h n^2 / \log n)$, where $h \le 1$ is the entropy of the text. We also present an algorithm for comparing two {run-length} encoded strings of length m and n, compressed into m' and n' runs, respectively, in O(m'n + n'm) complexity. This result extends to all distance or similarity scoring schemes that use an additive gap penalty.

International audience

We give a new text-compression scheme based on forbidden words ("antidictionary"). We prove that our algorithms attain the entropy for balanced binary sources. They run in linear time. Moreover, one of the main advantages of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and allows parallel compression. The techniques used in this paper are from information theory and finite automata.

We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size m h x m w in a text array of size n h x n w in the concurrent-read-concurrent-write--parallel-random-access-machine (CRCW--PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(n h x n w ) work, following preprocessing of the pattern. This improves the previous best bound of O(log log m ) time with optimal work [A. Amir, G. Benson, and M. Farach, Proceedings 5th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1993, pp. 79--85], following preprocessing of the pattern, where m=max{m h , m w }. The preprocessing required by our algorithm (and that due to Amir, Benson, and Farach) can be accomplished in O(log log m) time and O(m h x m w ) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].

Given a pattern string of length m for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log 2 m / log log m). We use this algorithm to obtain the following results (all algorithms below are optimal parallel algorithms on a CRCW PRAM): a deterministic string-matching algorithm which takes O(log log m) time for preprocessing and constant time for text search, which are the best possible in both preprocessing and text search; a constant-time deterministic string-matching algorithm in the case where the text length n satisfies $n=\Omega(m^{1+\epsilon})$ for a constant $\epsilon > 0$; a simple string-matching algorithm that has constant time with high probability for random input; the main result: a constant-expected-time Las Vegas algorithm for computing the period of the pattern and all witnesses and thus for string matching itself; in both cases, an $\Omega(\log\log m)$ lower bound is known for deterministic algorithms.

All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/>0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching.>

A new string-matching algorithm is presented, which can be viewed as an intermediate between the classical algorithms of Knuth, Morris, and Pratt on the one hand and Boyer and Moore, on the other hand.The algorithm is linear in time and uses constant space as the algorithm of Galil and Seiferas.It presents the advantage of being remarkably simple which consequently makes its analysis possible.The algorithm relies on a previously known result in combinatorics on words, called the Critical Factorization Theorem, which relates the global period of a word to Its local repetitions of blocks Categories and Subject Descriptors: D.