Maxime Crochemore

TCS Journal 2026 Journal Article

Internal quasiperiod queries

• Maxime Crochemore
• Costas S. Iliopoulos
• Jakub Radoszewski
• Wojciech Rytter
• Juliusz Straszyński
• Tomasz Waleń
• Wiktor Zuba

Internal pattern matching requires one to answer queries about factors of a given string. Many results are known on answering internal period queries, asking for the periods of a given factor. In this paper we investigate internal queries asking for covers (also known as quasiperiods) of a given factor. Let n denote the length of the string and m denote the length of the factor in question. We propose a data structure that answers such queries in O ( log m ) time for the shortest cover and in O ( log m log log m ) time for a representation of all the covers, after O ( n log n ) time and space preprocessing. This is a full version of a conference paper at SPIRE 2020 with query complexities improved by a log log n-factor and additional applications.

TCS Journal 2026 Journal Article

Quasi-linear-time algorithm for a longest common circular factor

• Mai Alzamel
• Maxime Crochemore
• Costas S. Iliopoulos
• Tomasz Kociumaka
• Jakub Radoszewski
• Wojciech Rytter
• Juliusz Straszyński
• Tomasz Waleń

We consider the Longest Common Circular Factor (LCCF) problem in which, given strings S and T of length at most n, we are to compute the longest factor of S whose cyclic shift is a factor of T. This new similarity measure is an extension of the classic Longest Common Factor. We show an algorithm solving the LCCF problem in O ( n log 3 n log ( r + 2 ) ) time, where r ≤ n is the length of the output, using O ( n ) space. A naive algorithm works in Ω(n 2) time, and no O ( n polylog n ) -time solution was known prior to our work. Our result constitutes yet another application of string synchronizing sets of Kempa and Kociumaka (STOC 2019). Compared to the preliminary version published at CPM 2019, we significantly simplified the algorithm and improved the space complexity from O ( n log 2 n ) to O ( n ). We achieved that with new algorithmic insights into a certain geometric intersection problem, solved by suitably decomposing intervals.

TCS Journal 2022 Journal Article

Checking whether a word is Hamming-isometric in linear time

• Marie-Pierre Béal
• Maxime Crochemore

A finite word f is Hamming-isometric if for any two words u and v of the same length avoiding f, u can be transformed into v by changing one by one all the letters on which u differs from v, in such a way that all of the new words obtained in this process also avoid f. Words which are not Hamming-isometric have been characterized as words having a border with two mismatches. We derive from this characterization a linear-time algorithm to check whether a word is Hamming-isometric. It is based on pattern matching algorithms with k mismatches. Lee-isometric words over a four-letter alphabet have been characterized as words having a border with two Lee-errors. We derive from this characterization a linear-time algorithm to check whether a word over an alphabet of size four is Lee-isometric.

I&C Journal 2022 Journal Article

Linear construction of a left Lyndon tree

• Golnaz Badkobeh
• Maxime Crochemore

We extend the left-to-right Lyndon factorisation of a word to the left Lyndon tree construction of a Lyndon word. It yields an algorithm to sort the prefixes of a Lyndon word according to the infinite ordering defined by Dolce et al. (2019). A straightforward variant computes the left Lyndon forest of a word. All algorithms run in linear time on a general alphabet, that is, in the letter-comparison model.

TCS Journal 2021 Journal Article

Shortest covers of all cyclic shifts of a string

• Maxime Crochemore
• Costas S. Iliopoulos
• Jakub Radoszewski
• Wojciech Rytter
• Juliusz Straszyński
• Tomasz Waleń
• Wiktor Zuba

A factor C of a string S is called a cover of S, if each position of S is contained in an occurrence of C. Breslauer (1992) [3] proposed a well-known O ( n ) -time algorithm that computes the shortest cover of every prefix of a string of length n. We show an O ( n log ⁡ n ) -time and O ( n ) -space algorithm that computes the shortest cover of every cyclic shift of a string of length n and an O ( n ) -time algorithm that computes the shortest among these covers. We also provide a combinatorial characterization of shortest covers of cyclic shifts of Fibonacci strings that leads to efficient algorithms for computing these covers. We further consider the bound on the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is Θ ( log ⁡ n ) for Fibonacci strings.

I&C Journal 2020 Journal Article

Absent words in a sliding window with applications

• Maxime Crochemore
• Alice Héliou
• Gregory Kucherov
• Laurent Mouchard
• Solon P. Pissis
• Yann Ramusat

An absent word of a word y is a word that does not occur in y. It is then called minimal if all its proper factors occur in y. In fact, minimal absent words (MAWs) provide useful information about y and thus have several applications. In this paper, we propose an algorithm that maintains the set of MAWs of a fixed-length window sliding over y online. Our algorithm represents MAWs through nodes of the suffix tree. Specifically, the suffix tree of the sliding window is maintained using modified Senft's algorithm (Senft, 2005), itself generalizing Ukkonen's online algorithm (Ukkonen, 1995). We then apply this algorithm to the approximate pattern-matching problem under the Length Weighted Index distance (Chairungsee and Crochemore, 2012). This results in an online O ( σ | y | ) -time algorithm for finding approximate occurrences of a word x in y, | x | ≤ | y |, where σ is the alphabet size.

TCS Journal 2020 Journal Article

Cartesian and Lyndon trees

• Maxime Crochemore
• Luís M.S. Russo

The article describes the structural and algorithmic relations between Cartesian trees and Lyndon trees. This leads to a uniform presentation of the Lyndon table of a word corresponding to the Next Nearest Smaller table of a sequence of numbers. It shows how to efficiently compute runs, that is, maximal periodicities occurring in a word.

I&C Journal 2019 Journal Article

Optimal bounds for computing α-gapped repeats

• Maxime Crochemore
• Roman Kolpakov
• Gregory Kucherov

Following (Kolpakov et al. , 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors of the form uvu with | u v | = | u | + | v | ≤ α | u |. Our main result is the O ( α n ) bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O ( α 2 n ) in (Kolpakov et al. , 2013). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1 + δ and 2), our result implies the O ( n / δ ) bound on their number, which improves the bound of (Kolpakov et al. , 2010) by a log ⁡ n factor. We also prove an algorithmic time bound O ( α n + S ) (S size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al. , 2015) of the same bound. Together with our bound on S, this implies an O ( α n ) -time algorithm for computing all maximal α-gapped repeats.

TCS Journal 2019 Journal Article

Special issue in honor of the 70th birthday of Prof. Wojciech Rytter

• Maxime Crochemore
• Jakub Radoszewski

TCS Journal 2018 Journal Article

Advances in Algorithms & Combinatorics on Strings (Honoring 60th birthday for Prof. Costas S. Iliopoulos)

• Maxime Crochemore
• Solon P. Pissis

I&C Journal 2018 Journal Article

Alignment-free sequence comparison using absent words

• Panagiotis Charalampopoulos
• Maxime Crochemore
• Gabriele Fici
• Robert Mercaş
• Solon P. Pissis

Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as q-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an absent word of some sequence if it does not occur in the sequence. An absent word is minimal if all its proper factors occur in the sequence. Here we present the first linear-time and linear-space algorithm to compare two sequences by considering all their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences. We also present an algorithm that, given a word x of length n, computes the largest integer for which all factors of x of that length occur in some minimal absent word of x in time and space O ( n ). Finally, we show that the known asymptotic upper bound on the number of minimal absent words of a word is tight.

TCS Journal 2017 Journal Article

Counting maximal-exponent factors in words

• Golnaz Badkobeh
• Maxime Crochemore
• Robert Mercaş

This article shows tight upper and lower bounds on the number of occurrences of maximal-exponent factors occurring in a word.

TCS Journal 2017 Journal Article

Covering problems for partial words and for indeterminate strings

• Maxime Crochemore
• Costas S. Iliopoulos
• Tomasz Kociumaka
• Jakub Radoszewski
• Wojciech Rytter
• Tomasz Waleń

Indeterminate strings are a subclass of non-standard words having non-deterministic nature. In a classic string every position contains exactly one symbol—we say it is a solid symbol—while in an indeterminate string a position may contain a set of symbols (possible at this position); such sets are called non-solid symbols. The most important subclass of indeterminate strings are partial words, where each non-solid symbol is the whole alphabet; in this case non-solid symbols are also called don't care symbols. We consider the problem of finding a shortest cover of an indeterminate string, i. e. , finding a shortest solid string whose occurrences cover the whole indeterminate string. We show that this classical problem becomes NP-complete for indeterminate strings and even for partial words. The proof of this fact is one of the main results of this paper. Our other main results focus on design of algorithms efficient with respect to certain parameters of the input (so called FPT algorithms) for the shortest cover problem. For the indeterminate string covering problem we obtain an O ( n k 2 + 2 k k 3 ) -time algorithm, where k is the number of non-solid symbols, while for the partial word covering problem we obtain a running time of O ( n k 2 + 2 O ( k log ⁡ k ) ). Additionally, we prove that, unless the Exponential Time Hypothesis is false, no 2 o ( k ) n O ( 1 ) -time solution exists for either problem, which shows that our algorithm for partial words is close to optimal. We also present an algorithm for both problems parameterized both by k and the alphabet size with a simple implementation. A preliminary version of this article was presented at the 25th International Symposium on Algorithms and Computation (ISAAC 2014), LNCS, vol. 8889, pp. 220–232, Springer (2014) [12].

TCS Journal 2017 Journal Article

Locating maximal approximate runs in a string

• Mika Amit
• Maxime Crochemore
• Gad M. Landau
• Dina Sokol

An exact run in a string T is a non-empty substring of T that is a repetition of a smaller substring possibly followed by a prefix of it. Finding maximal exact runs in strings is an important problem and therefore a well-studied one in the area of stringology. For a given string T of length n, finding all maximal exact runs in the string can be done in O ( n log ⁡ n ) time on general ordered alphabets or O ( n ) time on integer alphabets. In this paper, we investigate the maximal approximate runs problem: for a given string T and a number k, find non-empty substrings T ′ of T such that changing at most k letters in T ′ transforms them into a maximal exact run. We present an O ( n k 2 log 2 ⁡ k + o c c ) algorithm to solve this problem, where occ is the number of substrings found.

TCS Journal 2016 Journal Article

Efficient computation of maximal anti-exponent in palindrome-free strings

• Golnaz Badkobeh
• Maxime Crochemore
• Manal Mohamed
• Chalita Toopsuwan

A palindrome is a string x = a 1 ⋯ a n which is equal to its reversal x ˜ = a n ⋯ a 1. We consider gapped palindromes which are strings of the form u v u ˜, where u, v are strings, | v | ≥ 2, and u ˜ is the reversal of u. Replicating the standard notion of string exponent, we define the anti-exponent of a gapped palindrome u v u ˜ as the quotient of | u v u ˜ | by | u v |. To get an efficient computation of maximal anti-exponent of factors in a palindrome-free string, we apply techniques based on the suffix automaton and the reversed Lempel–Ziv factorisation. Our algorithm runs in O ( n ) time on a fixed-size alphabet or O ( n log ⁡ σ ) on a large alphabet, which dramatically outperforms the naive cubic-time solution.

EAAI Journal 2016 Journal Article

Linear algorithm for conservative degenerate pattern matching

• Maxime Crochemore
• Costas S. Iliopoulos
• Ritu Kundu
• Manal Mohamed
• Fatima Vayani

A degenerate symbol x ˜ over an alphabet Σ is a non-empty subset of Σ, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P ˜ and T ˜ of total length n containing k non-solid symbols in total, the occurrences of P ˜ in T ˜ in O(nk) time.

TCS Journal 2016 Journal Article

Linear-size suffix tries

• Maxime Crochemore
• Chiara Epifanio
• Roberto Grossi
• Filippo Mignosi

Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w |, a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and links for suffix tries in the worst case because of their unary nodes. It is an interesting question if the suffix trie can be stored using O ( n ) nodes. We present the linear-size suffix trie, which guarantees O ( n ) nodes. We use a new technique for reducing the number of unary nodes to O ( n ), that stems from some results on antidictionaries. For instance, by using the linear-size suffix trie, we are able to check whether a pattern p of length m = | p | occurs in w in O ( m log ⁡ | Σ | ) time and we can find the longest common substring of two strings w 1 and w 2 in O ( ( | w 1 | + | w 2 | ) log ⁡ | Σ | ) time for an alphabet Σ.

TCS Journal 2016 Journal Article

On the density of Lyndon roots in factors

• Maxime Crochemore
• Robert Mercaş

This work takes another look at the number of runs that a string may contain and provides an alternative proof for the bound. We also propose another stronger conjecture that states the following: for a fixed order on the alphabet, within every factor of a word there are at most as many occurrences of Lyndon roots corresponding to runs in the word as the length of the factor. Only first occurrences of roots in each run are considered.

TCS Journal 2016 Journal Article

Order-preserving indexing

• Maxime Crochemore
• Costas S. Iliopoulos
• Tomasz Kociumaka
• Marcin Kubica
• Alessio Langiu
• Solon P. Pissis
• Jakub Radoszewski
• Wojciech Rytter

Kubica et al. [33] and Kim et al. [29] introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same ‘shape’ as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in O ( n log ⁡ log ⁡ n ) expected time or in O ( n log 2 ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) worst-case time. It is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an O ( n log ⁡ n ) -time algorithm constructing complete order-preserving suffix trees.

TCS Journal 2014 Journal Article

Note on the greedy parsing optimality for dictionary-based text compression

• Maxime Crochemore
• Alessio Langiu
• Filippo Mignosi

Dynamic dictionary-based compression schemes are the most daily used data compression schemes since they appeared in the foundational paper of Ziv and Lempel in 1977, commonly referred to as LZ77. In dynamic setting, LZ77 considers a portion of the previous text as a dictionary and it uses a greedy approach to select, at each step, the longest match between the text and the dictionary. Compression is achieved by replacing matches with encoded dictionary pointers. LZ77 is the base of gzip, zip, rar, 7zip and many others compression software. All these compression schemes use variants of the greedy approach to parse (or factorise) the text into dictionary phrases. Greedy parsing optimality with respect to the number of phrases was proved by Storer et al. (1982) for unbounded LZ77-based dictionaries and by Cohn et al. (1996) for static suffix-closed dictionaries. The optimality of the greedy parsing was never proved for bounded size dictionary which is actually required by all of these practical schemes. In this article, we define the suffix-closed property for dynamic dictionaries, and we show that LZ77-based compression schemes, including the bounded dictionary variants, satisfy this property. Under this condition we prove the optimality of the greedy parsing as a variant of the proof by Cohn et al.

TCS Journal 2014 Journal Article

On the average number of regularities in a word

• Manolis Christodoulakis
• Michalis Christou
• Maxime Crochemore
• Costas S. Iliopoulos

We study the average number of powers and runs occurring in a word of length n drawn from an alphabet of size σ. We show that a word contains n σ ( r − 1 ) − 1 + o ( n ) powers of exponent r, at most n σ + o ( n ) runs, and also ( 1 + 2 σ − 1 ) n + o ( n ) palindromes. We also explore their abelian variants and prove that a binary word contains Θ ( n 3 2 ) abelian squares on the average, while its number of abelian cubes is related to Franel numbers. Finally, as a consequence, we show that a binary word has almost surely O ( n 3 2 ) abelian squares.

TCS Journal 2012 Journal Article

Improved algorithms for the range next value problem and applications

• Maxime Crochemore
• Costas S. Iliopoulos
• Marcin Kubica
• M. Sohel Rahman
• German Tischler
• Tomasz Waleń

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. [Maxime Crochemore, Costas S. Iliopoulos, M. Sohel Rahman, Finding patterns in given intervals, in: Antonin Kucera, Ludek Kucera (Eds.), MFCS, 22 in: Lecture Notes in Computer Science, vol. 4708, Springer, 2007, pp. 645–656]. In this paper, we present improved algorithms for problem RNV and algorithms for extended versions of the RNV problem. 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.

TCS Journal 2012 Journal Article

Using minimal absent words to build phylogeny

• Supaporn Chairungsee
• Maxime Crochemore

An absent word in a sequence is a segment that does not occur in the given sequence. It is a minimal absent word if all its proper factors occur in the given sequence. In this paper, we review the concept of minimal absent words, which includes the notion of shortest absent word. We present an efficient method for computing the minimal absent words of bounded length using a trie of bounded depth, representing bounded length factors. This method produces the minimal absent words of given bounded length, and furthermore our technique provides a linear-time algorithm with less memory usage than previous solutions. We also present an approach, the length-weighted index, to distinguish sequences of different organisms using their minimal absent words. The results show that we can build a phylogenetic tree based on the information collected.

I&C Journal 2011 Journal Article

Reactive automata

• Maxime Crochemore
• Dov M. Gabbay

A reactive automaton has extra links whose role is to change the behaviour of the automaton. We show that these links do not increase the expressiveness of finite automata but that they can be used to reduce dramatically their state number both in the deterministic case and the non-deterministic case. Typical examples of regular expressions associated with deterministic automata of exponential size according to the length of the expression show that reactive links provide an alternative representation of total linear size for the language.

TCS Journal 2011 Journal Article

The “runs” conjecture

• Maxime Crochemore
• Lucian Ilie
• Liviu Tinta

The “runs” conjecture, proposed by Kolpakov and Kucherov (1999) [7], states that the number of occurrences of maximal repetitions (runs) in a string of length n, runs ( n ), is at most n. We almost solve the conjecture by proving that runs ( n ) ⩽ 1. 029 n. This bound is obtained using a combination of theory and computer verification.

I&C Journal 2010 Journal Article

Fast computation of a longest increasing subsequence and application

• Maxime Crochemore
• Ely Porat

We consider the complexity of computing a longest increasing subsequence (LIS) parameterised by the length of the output. Namely, we show that the maximal length k of an increasing subsequence of a permutation of the set of integers { 1, 2, …, n } can be computed in time O ( n log log k ) in the RAM model, improving the previous 30-year bound of O ( n log k ). The algorithm also improves on the previous O ( n log log n ) bound. The optimality of the new bound is an open question. Reducing the computation of a longest common subsequence (LCS) between two strings to an LIS computation leads to a simple O ( r log log k ) -time algorithm for two sequences having r pairs of matching symbols and an LCS of length k.

TCS Journal 2009 Journal Article

Repetitions in strings: Algorithms and combinatorics

• Maxime Crochemore
• Lucian Ilie
• Wojciech Rytter

The article is an overview of basic issues related to repetitions in strings, concentrating on algorithmic and combinatorial aspects. This area is important both from theoretical and practical points of view. Repetitions are highly periodic factors (substrings) in strings and are related to periodicities, regularities, and compression. The repetitive structure of strings leads to higher compression rates, and conversely, some compression techniques are at the core of fast algorithms for detecting repetitions. There are several types of repetitions in strings: squares, cubes, and maximal repetitions also called runs. For these repetitions, we distinguish between the factors (sometimes qualified as distinct) and their occurrences (also called positioned factors). The combinatorics of repetitions is a very intricate area, full of open problems. For example we know that the number of (distinct) primitively-rooted squares in a string of length n is no more than 2 n − Θ ( log n ), conjecture to be n, and that their number of occurrences can be Θ ( n log n ). Similarly we know that there are at most 1. 029 n and at least 0. 944 n maximal repetitions and the conjecture is again that the exact bound is n. We know almost everything about the repetitions in Sturmian words, but despite the simplicity of these words, the results are nontrivial. One of the main motivations for writing this text is the development during the last couple of years of new techniques and results about repetitions. We report both the progress which has been achieved and which we expect to happen.

TCS Journal 2008 Journal Article

Approximating the 2-interval pattern problem

• Maxime Crochemore
• Danny Hermelin
• Gad M. Landau
• Dror Rawitz
• Stéphane Vialette

We address the issue of approximating the 2-Interval Pattern problem over its various models and restrictions. This problem, motivated by RNA secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified geometric constraints. We present several constant factor approximation algorithms whose performance guarantee depends on the different possible restrictions imposed on the input 2-interval set. In addition, we show that our results extend to the weighted variant of the problem.

MFCS Conference 2007 Conference Paper

Analysis of Maximal Repetitions in Strings

• Maxime Crochemore
• Lucian Ilie

Abstract The cornerstone of any algorithm computing all repetitions in strings of length n in \({\mathcal O}(n)\) time is the fact that the number of maximal repetitions (runs) is linear. Therefore, the most important part of the analysis of the running time of such algorithms is counting the number of runs. Kolpakov and Kucherov [FOCS’99] proved it to be cn but could not provide any value for c. Recently, Rytter [STACS’06] proved that c ≤ 5. His analysis has been improved by Puglisi et al. to obtain 3. 48 and by Rytter to 3. 44 (both submitted). The conjecture of Kolpakov and Kucherov, supported by computations, is that c = 1. Here we improve dramatically the previous results by proving that c ≤ 1. 6 and show how it could be improved by computer verification down to 1. 18 or less. While the conjecture may be very difficult to prove, we believe that our work provides a good approximation for all practical purposes. For the stronger result concerning the linearity of the sum of exponents, we give the first explicit bound: 5. 6 n. Kolpakov and Kucherov did not have any and Rytter considered “unsatisfactory” the bound that could be deduced from his proof. Our bound could be as well improved by computer verification down to 2. 9 n or less.

MFCS Conference 2007 Conference Paper

Finding Patterns in Given Intervals

• Maxime Crochemore
• Costas S. Iliopoulos
• M. Sohel Rahman

Abstract 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 cases, we develop solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem.

TCS Journal 2006 Journal Article

Longest repeats with a block of k don’t cares

• Maxime Crochemore
• Costas S. Iliopoulos
• Manal Mohamed
• Marie-France Sagot

A k-repeat is a string w k = u * k v that matches more than one substring of x, where * is the don’t care letter and k > 0. We propose an O ( n log n ) -time algorithm for computing all longest k-repeats in a given string x = x [ 1. . n ]. The proposed algorithm uses suffix trees to fulfill this task and relies on the ability to answer lowest common ancestor queries in constant time.

TCS Journal 2005 Journal Article

A note on the Burrows–Wheeler transformation

• Maxime Crochemore
• Jacques Désarménien
• Dominique Perrin

We relate the Burrows–Wheeler transformation with a result in combinatorics on words known as the Gessel–Reutenauer transformation.

TCS Journal 2004 Journal Article

Two-dimensional pattern matching with rotations

• Amihood Amir
• Ayelet Butman
• Maxime Crochemore
• Gad M. Landau
• Mary Schaps

The problem of pattern matching with rotation is that of finding all occurrences of a two-dimensional pattern in a text, in all possible rotations. We prove an upper and lower bound on the number of such different possible rotated patterns. Subsequently, given an m×m array (pattern) and an n×n array (text) over some finite alphabet Σ, we present a new method yielding an O(n 2 m 3) time algorithm for this problem.

MFCS Conference 2003 Conference Paper

A Basis of Tiling Motifs for Generating Repeated Patterns and Its Complexity for Higher Quorum

• Nadia Pisanti
• Maxime Crochemore
• Roberto Grossi
• Marie-France Sagot

Abstract We investigate the problem of determining the basis of motifs (a form of repeated patterns with don’t cares) in an input string. We give new upper and lower bounds on the problem, introducing a new notion of basis that is provably smaller than (and contained in) 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 these bases grows exponentially with the quorum, the minimal number of times a motif must appear. We show that a polynomial-time algorithm exists only for fixed quorum.

TCS Journal 2003 Journal Article

Reducing space for index implementation

• Maxime Crochemore

This article considers several strategies to implement efficiently full indexes on raw textual data. Indexes are based on representations of all the suffixes of the original text, for which we describe three types of implementations aimed at reducing the memory space. The first method is a combination of compaction and minimization that leads to the compact suffix automaton. As a second method we show that considering a complement language can be useful especially when it is related to data compression. Finally, approximation of the set of suffixes is the third technique used to reduce the space of the implementation.

SODA Conference 2002 Conference Paper

A sub-quadratic sequence alignment algorithm for unrestricted cost matrices

• Maxime Crochemore
• Gad M. Landau
• Michal Ziv-Ukelson

TCS Journal 1999 Journal Article

Constant-space string-matching in sublinear average time

• Maxime Crochemore
• Leszek Ga̧sieniec
• Wojciech Rytter

Given two strings: pattern P of length m and text T of length n. The string-matching problem is to find all occurrences of the pattern P in the text T. We present a string-matching algorithms which works in o(n) average time and constant additional space for one-dimensional texts and two-dimensional arrays. This is a first attempt to the small-space string-matching problem in which sublinear time algorithms are achieved. We show that all occurrences of one- or two-dimensional patterns can be found in O( n r ) average time with constant memory, where r is the repetition size of P (size of the longest repeated subword of P).

MFCS Conference 1998 Conference Paper

Minimal Forbidden Words and Factor Automata

• Maxime Crochemore
• Filippo Mignosi
• Antonio Restivo

Abstract Let L(M) be the (factorial) language avoiding a given anti-factorial language M. We design an automaton accepting L(M) and built from the language M. The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.

TCS Journal 1994 Journal Article

On two-dimensional pattern matching by optimal parallel algorithms

• Maxime Crochemore
• Wojciech Rytter

Simplified versions of Kedem–Landau–Palem algorithms for parallel one-dimensional and two-dimensional pattern-matching on a CRCW PRAM are presented. We show that the only nontrivial part of KLP algorithm is the preprocessing part: computation of consistent names of very small factors. The crucial part in KLP algorithm is a suffix–prefix matching subprocedure. In our algorithm such a subprocedure is avoided. A novel algorithm for 2-dimensional matching is presented which is more directly designed for two-dimensional objects. It does not use the multi-text/multi-pattern approach as in KLP algorithm. Techniques for constructing parallel image identification algorithms are introduced: cutting images into small factors, and compressing images by a parallel reduction of a large number of such independent factors into smaller objects. The importance of five types of factors is emphasized. A new useful type of two-dimensional factors is introduced: thin factors.

FOCS Conference 1993 Conference Paper

Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions

• Richard Cole 0001
• Maxime Crochemore
• Zvi Galil
• Leszek Gasieniec
• Ramesh Hariharan
• S. Muthukrishnan 0001
• Kunsoo Park
• Wojciech Rytter

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

TCS Journal 1992 Journal Article

Foreword

• Maxime Crochemore

TCS Journal 1992 Journal Article

String-matching on ordered alphabets

• Maxime Crochemore

We present a new string-matching algorithm that exploits an ordering of the alphabet. The algorithm is linear in time and uses a fixed number of memory locations in addition to the text and the pattern. Therefore, it is time-space optimal. Its main characteristic is that it scans the pattern from left to right. No preprocessing of the pattern is needed and the complexity is independent of the size of the pattern. An important consequence is the possibility of computing the periods of a word in linear time and constant space. The algorithm can also be turned into a real-time string-matching algorithm.

TCS Journal 1991 Journal Article

On the parallel recognition of unambiguous context-free languages

• Michal Chytil
• Maxime Crochemore
• Burkhard Monien
• Wojciech Rytter

We present a simple parallel algorithm recognizing unambiguous context-free languages on a CREW PRAM in time log2 n with only n 3 processors. This gives the smallest number of processors known for the recognition of unambiguous context-free languages in polylogarithmic time. Using the same framework a new algorithm is also given for the recognition of deterministic context-free languages in log2 n time with quadratic number of processors.

TCS Journal 1991 Journal Article

Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays

• Maxime Crochemore
• Wojciech Rytter

The Karp-Miller-Rosenberg (1972) algorithm was one of the first efficient (almost linear) sequential algorithms for finding repeated patterns and for string matching. In the area of efficient sequential computations on strings it was soon superseded by more efficient (and more sophisticated) algorithms. We show that the Karp-Miller-Rosenberg algorithm (KMR) must be considered as a basic technique in parallel computations. For many problems, variations of KMR give the (known) most efficient parallel algorithms. The representation of the set of basic factors (subarrays) of a string (array) produced by the algorithm is an extremely useful data structure in parallel algorithms on strings and arrays. This gives also a general unifying framework for a large variety of problems. We show that the following problems for strings and arrays can be solved by almost optimal parallel algorithms: pattern-matching, longest repeated factor (subarray), longest common factor (subarray), maximal symmetric factor (subarray). Also the following problems for strings can be solved within the same complexity bounds: finding squares, testing even palstars and compositions of k palindromes for k=2, 3, 4, computing Lyndon factorization and building minimal pattern-matching automata. In the model without concurrent writes the parallel time is O(log(n)2) (with n processors) and in the model with concurrent writes the time, for most of the problems, is O(log(n)) (with n processors). For two problems related to the one-dimensional case (longest repeated factor and longest common factor) there were designed parallel algorithms using suffix trees (Apostolico et al. 1988). However, our data structure is simpler and, furthermore, for the two-dimensional case suffix trees do not work. The complexity of our algorithms does not depend on the size of the alphabet, except for the computation of pattern-matching automata.

MFCS Conference 1990 Conference Paper

Parallel Construction of Minimal Suffix and Factor Automata

• Maxime Crochemore
• Wojciech Rytter

Abstract The main result of the paper is an efficient parallel construction of factor automata. We show that the construction of directed acyclic word graphs (dawg's) and of minimal suffix and minimal factor automata can be done by almost optimal parallel algorithms (optimal within logarithmic factor). Our constructions have the same parallel complexity as the best known parallel algorithms computing suffix trees. We exploit a simple relation between dawg's and suffix trees.

MFCS Conference 1988 Invited Paper

String Matching with Constraints

• Maxime Crochemore

TCS Journal 1986 Journal Article

Transducers and repetitions

• Maxime Crochemore

The factor transducer of a word associates to each of its factors (or subwords) their first occurrence. Optimal bounds on the size of minimal factor transducers together with an algorithm for building them are given. Analogue results and a simple algorithm are given for the case of subsequential suffix transducers. Algorithms are applied to repetition searching in words.