Thierry Lecroq



List of publications

Complete list in

International journals with refereing

M. Salson, T. Lecroq, M. Léonard and L. Mouchard

Dynamic Extended Suffix Arrays

Journal of Discrete Algorithms 8(2) (2010) 241-257. DOI.
S. Faro and T. Lecroq

Efficient Variants of the Backward-Oracle-Matching Algorithm

International Journal of Foundations of Computer Science 20(6) (2009) 967-984. DOI.
M. Salson, T. Lecroq, M. Léonard and L. Mouchard

A Four-Stage Algorithm for Updating a Burrows-Wheeler Transform

Theoretical Computer Science 410(43) (2009) 4350-4359. Special issue for Maxime Crochemore's 60th Birthday, DOI.
J.-P. Duval, T. Lecroq and A. Lefebvre

Efficient validation and construction of border arrays and validation of string matching automata

RAIRO-Theoretical Informatics and Applications 43(2) (2009) 281-297.
É. Prieur and T. Lecroq

On-line construction of compact suffix vectors and maximal repeats

Theoretical Computer Science 407(1-3) (2008) 290-301.
T. Lecroq

Fast exact string matching algorithms

Information Processing Letters 102(6) (2007) 229-235.
É. Prieur and T. Lecroq

From Suffix Trees to Suffix Vectors

International Journal of Foundations of Computer Science 17(6) (2006) 1385-1402.
J.-P. Duval, T. Lecroq and A. Lefebvre

Border Array on Bounded Alphabet

Baba au rhum
Journal of Automata, Languages and Combinatorics 10(1) (2005) 51-60.
J.-P. Duval, R. Kolpakov, G. Kucherov, T. Lecroq and A. Lefebvre

Linear-Time Computation of Local Periods

Theoretical Computer Science 326(1-3) (2004) 229-240.
A. Lefebvre, T. Lecroq and J. Alexandre

An improved algorithm for finding longest repeats with a modified factor oracle

Journal of Automata, Languages and Combinatorics 8(4) (2003) 647-658.
M. Crochemore, C.S. Iliopoulos, T. Lecroq, Y.J. Pinzon, W. Plandowski and W. Rytter

Occurrence and Substring Heuristics for delta-Matching

Fundamenta Informaticae 56(1-2) (2003) 1-21.
R. Cole, C.S. Iliopoulos, T. Lecroq, W. Plandowski and W. Rytter

On Special Families of Morphisms Related to delta-Matching and Don't Care Symbols

Information Processing Letters 85(5) (2003) 227-233.
A. Lefebvre, T. Lecroq, H. Dauchel and J. Alexandre

FORRepeats: detects repeats on entire chromosomes and between genomes

Bioinformatics 19(3) (2003) 319-326.
M. Crochemore, C. Hancart and T. Lecroq

A Unifying Look at the Apostolico-Giancarlo String-Matching Algorithm

Journal of Discrete Algorithms 1(1) (2003) 37-52.
A. Lefebvre and T. Lecroq

A heuristic for computing repeats with a factor oracle: Application to biological sequences

International Journal of Computer Mathematics 79(12) (2002) 1303-1315.
A. Lefebvre and T. Lecroq

Compror: on-line lossless compression with a factor oracle

Information Processing Letters 83(1) (2002) 1-6.
M. Crochemore, A. Czumaj, L. Gasieniec, T. Lecroq, W. Plandowski and W. Rytter

Fast practical multi-pattern matching

Information Processing Letters 71(3-4) (1999) 107-113.
T. Lecroq

Experiments on string matching in memory structures

Software Practice & Experience 28(5) (1998) 562-568.
T. Lecroq, J.-F. Myoupo and D. Semé

A one-phase parallel algorithm for the sequence alignment problem

Parallel Processing Letters 8(4) (1998) 515-526.
M. Crochemore and T. Lecroq

Tight bounds on the complexity of the Apostolico-Giancarlo algorithm

Information Processing Letters 63(4) (1997) 195-203.
T. Lecroq, G. Luce and J.-F. Myoupo

A faster linear systolic algorithm for recovering a longest common subsequence

Information Processing Letters 61(3) (1997) 129-136.
M. Crochemore and T. Lecroq

Pattern matching and text compression algorithms

ACM Computing Surveys 28 (1) (1996) 39-41.
T. Lecroq

Experimental results on string matching algorithms

Software Practice & Experience 25 (7) (1995) 727-765.
M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski and W. Rytter

Speeding-up two string matching algorithms

Algorithmica 12 (4/5) (1994) 247-267.
T. Lecroq

A variation on the Boyer-Moore algorithm

Theoretical Computer Science 92 (1) (1992) 119-144.

National journals with refereing

A. Pauchet, M. El Abed, T. Merabti, É. Prieur, T. Lecroq and .S.J. Darmoni

Identification de répétitions dans les navigations au sein d'un catalogue de santé

Revue d'Intelligence Artificielle, 23(1) (2009) 113-132.

International conferences with committee

T. El Falah, T. Lecroq and M. Elloumi

SMS-Forbid: An efficient algorithm for Simple Motif Problem

2nd International Conference on Bioinformatics and Computational Biology (BICoB 2010), Honolulu, Hawaii, USA, accepted.
T. Merabti, C. Letord, H. Abdoune, T. Lecroq, M. Joubert and S.J. Darmoni

Projection and inheritance of SNOMED CT Relations between MeSH Terms

Medical Informatics Europe (MIE 2009), Sarajevo, Bosnia and Herzegovina, Studies in Health Technology and Informatics, Volume 150, Pages 233-237, 2009.
S. Faro and T. Lecroq

An efficient matching algorithm for encoded DNA sequences and binary strings

In: (G. Kucherov and E. Ukkonen editors, Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009), Lille, France, 2009) Lecture Notes in Computer Science 5577, Springer-Verlag, Berlin, 106-115. DOI
M. Salson, T. Lecroq, M. Léonard and L. Mouchard

Dynamic Burrows-Wheeler Transform

In: Jan Holub and Jan Zdárek editors, Prague Stringology Conference 2008 (PSC 2008), Pages 13-25, 2008.
S. Faro and T. Lecroq

Efficient Variants of the Backward-Oracle-Matching Algorithm

In: Jan Holub and Jan Zdárek editors, Prague Stringology Conference 2008 (PSC 2008), Pages 146-160, 2008.
T. Merabti, S. Pereira, C. Letord, T. Lecroq, B. Dahamna, M. Joubert and S.J. Darmoni

Searching Related Resources in a Quality Controlled Health Gateway: a Feasibility Study

eHealth Beyond the Horizon - Get IT There - Proceedings of MIE2008 - The XXIst International Congress of the European Federation for Medical Informatics, Göteborg, Sweden, May, Studies in Health Technology and Informatics, Volume 136, Pages 235 - 240, 2008.
É. Prieur and T. Lecroq

On-line construction of compact suffix vectors and maximal repeats

Proceedings of the Mons Days of Theoretical Computer Science (JM 2006), Rennes, France, 2006, 311-322.
J.-P. Duval, T. Lecroq and A. Lefebvre

Efficient validation and construction of border arrays

Proceedings of the Mons Days of Theoretical Computer Science (JM 2006), Rennes, France, 2006, 179-189.
É. Prieur and T. Lecroq

From suffix trees to suffix vectors

Proceedings of the Prague Stringology Conference (PSC 2005), Prague, Tcheque Republic, 2005, 37-53.
J.-P. Duval, R. Kolpakov, G. Kucherov, T. Lecroq and A. Lefebvre

Linear-Time Computation of Local Periods

In: (B. Rovan and P. Vojtas editors, Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), Bratislava, Slovakia, 2003) LNCS 2747, Springer-Verlag, 388-397.
J.-P. Duval, T. Lecroq and A. Lefebvre

Border Array on Bounded Alphabet

Baba au rhum
In: (M. Balík and M. Simánek editors, Proceedings of the Prague Stringology Conference (PSC 2002), Prague, Tcheque Republic, 2002) Research Report DC-2002-03, 28-35.
A. Lefebvre, T. Lecroq and J. Alexandre

Drastic improvements over repeats found with a factor oracle

In: (E. Billington, D. Donovan and A. Khodkar editors, Proceedings of the 13th Australasian Workshop on Combinatorial Algorithms (AWOCA 2002), Fraser Island, Queensland, Australia, 2002) 253-265.
M. Crochemore, C.S. Iliopoulos, T. Lecroq, W. Plandowski and W. Rytter

Three Heuristics for delta-matching: delta-BM algorithms

In: (A. Apostolico and M. Takeda editors, Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching (CPM 2002), Fukuoka, Japan, 2002) LNCS 2373, Springer-Verlag, 178-189.
T. Lecroq, J.-F. Myoupo and D. Semé

Exact Computations of the Longest Repeated Suffix Ending at Each Point in a Word

In: (R. Gantenbein and S. Shin editors, Proceedings of the ISCA 17th International Conference on Computers and Their Applications (CATA-2002), San Francisco, California, 2002) 18-21.
M. Crochemore, C.S. Iliopoulos, T. Lecroq and Y.J. Pinzon

Approximate string matching in musical sequences

In: (M. Balík and M. Simánek editors, Proceedings of the Prague Stringology Conference (PSC 2001), Prague, République Tchèque, 2001) Annual Report DC-2001-06, 26-39.
R. Cole, C.S. Iliopoulos, T. Lecroq, W. Plandowski and W. Rytter

Relations between delta-matching and matching with don't care symbols: delta-distinguishing morphisms

In: (E. Tri Baskoro editor, Proceedings of the 12th Autralasian Workshop on Combinatorial Algorithms (AWOCA 2001), Bandung, Indonesia, 2001) 80-87.
A. Lefebvre and T. Lecroq

Estimating topological entropy of biological sequences using a factor oracle

In: (Proceedings of the 5th World Multi-Conference on Systemics, Cybernetics and Informatics (SCI 2001), Orlando, Florida, 2001).
C.S. Iliopoulos, T. Lecroq, L. Mouchard and Y.J. Pinzon

Computing Repetitions in Musical Sequences

In: (M. Balík and M. Simánek editors, Proceedings of the Prague Stringology Club Workshop (PSCW 2000), Prague, République Tchèque, 2000) Annual Report DC-2000-03, 49-59.
A. Lefebvre and T. Lecroq

Computing repeated factors with a factor oracle

In: (L. Brankovic and J. Ryan editors, Proceedings of the 11th Autralasian Workshop on Combinatorial Algorithms (AWOCA 2000), Hunter Valley, Australia, 2000) 145-158.
C. Charras and T. Lecroq

Java tools to help understanding pattern matching techniques

In: (D. C. Dimitrov editor, Proceedings of the 5th International Conference on Computer Aided Engineering Education (CAEE 1999), Sofia, Bulgaria, 1999) 105-111.
C. Charras and T. Lecroq

Exact string matching animation in Java

In: (J. Holub and M. Simánek editors, Proceedings of the Prague Stringology Club Workshop (PSCW 1998), Prague, Tcheque Republic, 1998) Collaborative Report DC-98-06, 36-43.
C. Charras, T. Lecroq and J. D. Pehoushek

A very fast string matching algorithm for small alphabets and long patterns

In: (M. Farach-Colton editor, Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching (CPM 1998), Piscataway, New Jersey, 1998) Lecture Notes in Computer Science 1448, Springer-Verlag, Berlin, 55-64.
M. Crochemore and T. Lecroq

Tight bounds on the complexity of the Apostolico-Giancarlo algorithm

In: (N. Ziviani, R. Baeza-Yates and K. Guimaraes editors, Proceedings of the Third South American Workshop on String Processing (WSP 1996), Recife, Brazil, 1996) Carleton University Press, Ottawa, Canada, 64-74.
M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski and W. Rytter

Speeding-up two string matching algorithms

In: (A. Finkel and M. Jantzen editors, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1992) , Cachan, France, 1992) Lecture Notes in Computer Science 577, Springer-Verlag, Berlin, 589-600.

Posters in international conferences with committee

S. Faro and T. Lecroq

Efficient Pattern Matching on Binary Strings

SOFSEM: 35th International Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic 2009.

Article or Poster

T. Merabti, S. Pereira, T. Lecroq, M. Joubert and S.J. Darmoni

Inheritance of SNOMED CT Relations between Concepts by two Health Terminologies (SNOMED International and ICD-10)

In: (R. Cornet and K.A. Spackman editors, Representing and sharing knowledge using SNOMED, Proceedings of the 3rd international conference on Knowledge Representation in Medicine (KR-MED 2008) Phoenix, AZ, 2008) 118.
A. Lefebvre and T. Lecroq

Compror: compression with a factor oracle

In: (J. A. Storer and M. Cohn editors, Proceedings of the Data Compression Conference (DCC 2001), Snowbird, Utah, 2001) IEEE Computer Society, 502.
T. Lecroq and J.-F. Myoupo

Détermination d'un plus long sous-mot commun à deux mots sur un réseau linéaire

In: (L. Bougé, M. Cosnard and P. Fraigniaud editors, Actes des 6èmes Rencontres Francophones du Parallélisme (RenPar 1994), Lyon, France, 1994) 301.

National conference with committee

É. Chanoni, T. Lecroq and A. Pauchet

Extraction de motifs dans des dialogues annotés par programmation dynamique

Actes des Cinquièmes Journées Francophones Modèles Formels de l'Interaction (MFI 2009), Lannion, France, 2009, 101-112.
T. Merabti, H. Abdoune, T. Lecroq, M. Joubert and S.J. Darmoni

Projection des relations SNOMED CT entre les termes de deux terminologies (CIM10 et SNOMED 3.5)

Risques, technologies de l'information pour les pratiques médicales : comptes rendus des treizièmes Journées Francophones d'Informatique Médicale (JFIM 2009), Nice, France, 2009, 79-88.
É. Chanoni, T. Lecroq and A. Pauchet

Une nouvelle heuristique pour l'alignement de motifs 2D par programmation dynamique

Actes des Journées Francophones de Planification, Décision et Apprentissage pour la conduite de systèmes (JFPDA 2008), Metz, France, 2008, 83-91.
J.-P. Duval, T. Lecroq and A. Lefebvre

Efficient validation and construction of Knuth-Morris-Pratt arrays

Knuth Days inBordeaux

Conference in honor of Donald E. Knuth, Bordeaux, France, 2007.
A. Lefebvre, T. Lecroq and J. Alexandre

Utilisations de l'oracle des facteurs

In: (L. Duret, C. Gaspin and T. Schiex editors, Actes des 2ème Journées Ouvertes Biologie Informatique Mathématiques (JOBIM 2001), Toulouse, France, 2001) 153-157.

Posters in national conferences with committee

É. Prieur and T. Lecroq

Des arbres de suffixes aux vecteurs de suffixes

Journées Ouvertes Biologie Informatique Mathématiques (JOBIM 2005), Lyon, France, 2005.

Article or Poster

Conference without committee

M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski and W. Rytter

Deux méthodes pour accélérer l'algorithme de Boyer-Moore

In: (D. Krob editor, Théorie des Automates et Applications, Actes des 2èmes Journées Franco-Belges, Rouen, France, 1991) PUR 176, Rouen, France, 45-63.

Invited talks

T. Lecroq

Theoretical and practical string matching

Proceedings of the 10th Australasian Workshop on Combinatorial Algorithms (AWOCA 1999), Perth, Western Australia, August 1999, p. 2.
T. Lecroq

The Boyer-Moore String Matching Algorithm and its Variants: A Survey

Prague Stringology Club Workshop (PSCW 1999), Prague, République Tchèque, 1999.
T. Lecroq

Theoretical and practical aspects of string matching

7th International Colloquium on Numerical Analysis and Computer Science with Applications (NACSA 1998), Plovdiv, Bulgarie,
Résumé p. 75.

Chapters in books

M. Crochemore and T. Lecroq

Algorithms and Theory of Computation Handbook

Text data compression algorithms

Algorithms and Theory of Computation Handbook, Second Edition, Volume 1: General Concepts and Techniques, (2009), Mikhail J. Atallah and Marina Blanton editors, Chapter 14, pages 14.1-14.25, CRC Press, Boca Raton, FL.
M. Crochemore and T. Lecroq

Encyclopedia of Database Systems

Suffix tree

Encyclopedia of Database Systems, Ling Liu and M. Tamer Özsu editors, (2009), Part 20, pages 2876-2880, Springer Verlag. DOI.
M. Crochemore and T. Lecroq

Encyclopedia of Database Systems

Trie

Encyclopedia of Database Systems, Ling Liu and M. Tamer Özsu editors, (2009), Part 20, pages 3179-3182, Springer Verlag. DOI.
M. Crochemore and T. Lecroq

Encyclopedia of Algorithms

Sequential Multiple String Matching

Encyclopedia of Algorithms, Ming-Yang Kao editor, (2008), pages 826-829, Springer Verlag.
M. Crochemore and T. Lecroq

Encyclopedia of Algorithms

Sequential Exact String Matching

Encyclopedia of Algorithms, Ming-Yang Kao editor, (2008), pages 824-826, Springer Verlag.
M. Crochemore and T. Lecroq

 New Developments in Formal Languages and Applications

Alignments and Approximate String Matching

New Developments in Formal Languages and Applications, Gemma Bel-Enguix, M. Dolores Jiménez-López and Carlos Martin-Vide editors, Series: Studies in Computational Intelligence, Volume 113, (2008), pages 59-93, Springer Verlag.
J.-P. Duval, A. Lefebvre and T. Lecroq

London Algorithmics and Stringology 2006

Efficient validation and construction of border arrays

London Algorithmics and Stringology 2006, J. Daykin, M. Mohamed and K. Steinhoefel editors, pages 135-147, King's College London Publications, Texts in Algorithms, Vol. 8 (2007).
M. Crochemore and T. Lecroq

 Recent Advances in Formal Languages and Applications

Text Searching and Indexing

Recent Advances in Formal Languages and Applications, Series: Studies in Computational Intelligence, Volume 25, (2006), Zoltan Esik, Carlos Martin-Vide and Victor Mitrana editors, pages 43-80, Springer Verlag.
T. Lecroq and A. Lefebvre

String Algorithmics

Different Applications of the Factor Oracle: An Overview

String Algorithmics, (2004), Costas S. Iliopoulos and Thierry Lecroq, editors, pages 129-154, King's College London Publications.
M. Crochemore and T. Lecroq

Computer Science Handbook

Pattern matching and text compression algorithms

Computer Science Handbook, (2004), Allen B. Tucker editor, chapter 13, pages 13.1-13.48, 2nd edition, Chapman & Hall/CRC Press, Bocca Raton, FL.
M. Crochemore and T. Lecroq

Algorithms and Theory of Computation Handbook

Text data compression algorithms

Algorithms and Theory of Computation Handbook, (1998), Mikhail J. Atallah editor, chapter 12, 12.1-12.23, CRC Press, Bocca Raton, FL.
M. Crochemore and T. Lecroq

The Computer Science and Engineering Handbook

Pattern matching and text compression algorithms

The Computer Science and Engineering Handbook, (1996), Allen B. Tucker, Jr. editor, chapter 8, pages 162-202, CRC Press, Bocca Raton, FL.

Books

M. Crochemore, C. Hancart and T. Lecroq

Algorithms on Strings

Algorithms on Strings

Cambridge University Press, 2007.
Costas S. Iliopoulos and Thierry Lecroq, editors,

String Algorithmics
String Algorithmics

King's College London Publications, 2004.
C. Charras and T. Lecroq

Handbook of Exact String Matching Algorithms
Handbook of Exact String Matching Algorithms

King's College London Publications, 2004.

html version with animation,
Postscript version.

M. Crochemore, C. Hancart and T. Lecroq

Algorithmique du texte

Algorithmique du texte

Vuibert, 2001.

Thesis

T. Lecroq

Quelques aspects de l'algorithmique du texte

Habilitation à Diriger des Recherches defended on December 8th, 2000 at the University of Rouen, France.
T. Lecroq

Recherches de mot

Ph.D. Thesis defended on February 18th, 1992 at the University of Orléans, France.

Reports

S. Faro and T. Lecroq

Efficient Pattern Matching on Binary Strings

Report arXiv:0810.2390, 2008.
C. Charras and T. Lecroq

Exact string matching animation in Java

Report LIR 97.10, Université de Rouen, 1997.
T. Lecroq, J.-F. Myoupo and D. Semé

A one-phase parallel algorithm for the sequence alignment problem

Report LaRIA 97-16, Université de Picardie Jules Verne, 1997.
T. Lecroq

Experimental results on string matching over infinite alphabets

Report LIR 97.01, Université de Rouen, 1997.
T. Lecroq, G. Luce and J.-F. Myoupo

A faster linear systolic algorithm for recovering a longest common subsequence

Report LaRIA 96-07, Université de Picardie Jules Verne, 1996.
M. Crochemore and T. Lecroq

Text data compression algorithms

Report LIR 96.15 Informatique Fondamentale, Université de Rouen, 1996.
M. Crochemore and T. Lecroq

Tight bounds on the complexity of the Apostolico-Giancarlo algorithm

Report LIR 96.12 Informatique Fondamentale, Université de Rouen, 1996.
M. Crochemore and T. Lecroq

Pattern matching and text compression algorithms

Report LIR 95.11 Informatique Fondamentale, Université de Rouen, 1995.
and
Report IGM 95-21, Université de Marne-la-Vallée, 1995.
T. Lecroq and J.-F. Myoupo

Détermination d'un plus long sous-mot commun à deux mots sur un réseau linéaire

Report LIR 95.08 Informatique Fondamentale, Université de Rouen, 1995.
T. Lecroq

Experimental results on string matching algorithms

Report LITP 94.12, Universités Paris 6 et 7, 1994.
M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski and W. Rytter

Fast practical multi-pattern matching

Report IGM 93-03, Université de Marne-la-Vallée, 1995.
M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski and W. Rytter

Speeding-up two string matching algorithms

Report LITP 92.21, Universités Paris 6 et 7, 1992.
T. Lecroq

Recherches de mot

Report LITP 92.15, Universités Paris 6 et 7, 1992.

Miscelleanous

E. Y. Harris, T. Lecroq, G. Kucherov and S. Lonardi

CPM's 20th Anniversary: A Statistical Retrospective

In: (G. Kucherov and E. Ukkonen editors, Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009), Lille, France, 2009) Lecture Notes in Computer Science 5577, Springer-Verlag, Berlin, 1-11. DOI
M. Crochemore and T. Lecroq

A fast implementation of the Boyer-Moore string matching algorithm

Manuscript, 2007.
T. Lecroq

Quelques aspects de l'algorithmique du texte

Technique et Science Informatiques 20(3) (2001) 279-281.
T. Lecroq

New experimental results on exact string-matching

Manuscript, 2000.
T. Lecroq

Une introduction à la recherche de mot

Proceedings of the School "Jeunes Chercheurs Algorithmique et Calcul Formel du GDR ALP", March 2000.
C. Charras and T. Lecroq

Sequence comparison

html version with animation,
PostScript version.
Thierry Lecroq
home page