, Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files, Proceedings of the 5th ACM-SIAM Annual Symposium on Discrete Algorithms, pp.705-714, 1994.
DOI : 10.1006/jcss.1996.0023
, The myriad virtues of suffix trees, Combinatorial Algorithms on Words, pp.85-96
, Monotony of Surprise and Large-Scale Quest for Unusual Words, Journal of Computational Biology, vol.10, issue.3-4, pp.283-311, 2003.
DOI : 10.1089/10665270360688020
, Efficient tools for comparative substring analysis, Journal of Biotechnology, vol.149, issue.3, pp.120-126, 2010.
DOI : 10.1016/j.jbiotec.2010.05.006
, Optimal off-line detection of repetitions in a string, Theoretical Computer Science, vol.22, issue.3, pp.297-315, 1983.
DOI : 10.1016/0304-3975(83)90109-3
, Data structures and algorithms for the string statistics problem, Algorithmica, vol.25, issue.3, pp.481-494, 1996.
DOI : 10.1145/321941.321946
URL : http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1465&context=cstech
, Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance, SIAM Journal on Computing, vol.26, issue.5, pp.1343-1362, 1997.
DOI : 10.1137/S0097539793246707
URL : http://juankm702.googlepages.com/parameterizedduplicationinstringsalg.pdf
, Minimal forbidden words and symbolic dynamics, STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science Proceedings, volume 1046 of Lecture Notes in Computer Science, pp.555-566, 1996.
DOI : 10.1007/3-540-60922-9_45
, The smallest automation recognizing the subwords of a text, Theoretical Computer Science, vol.40, issue.1, pp.31-55, 1985.
DOI : 10.1016/0304-3975(85)90157-4
,
, Solving the string statistics problem in time O(n log n) In Automata, Languages and Programming, 29th International Colloquium, Proceedings, pp.728-739, 2002.
, A block-sorting lossless data compression algorithm Digital Equipments Corporation Using minimal absent words to build phylogeny, Theoretical Computer Science, vol.450, issue.1, pp.109-116, 1994.
, Efficient suffix trees on secondary storage, Proceedings of the 7th ACM-SIAM Annual Symposium on Discrete Algorithms, pp.383-391, 1996.
, Transducers and repetitions, Theoretical Computer Science, vol.45, issue.1, pp.63-86, 1986.
DOI : 10.1016/0304-3975(86)90041-1
URL : https://hal.archives-ouvertes.fr/hal-00619540
, Automata and forbidden words, Information Processing Letters, vol.67, issue.3, pp.111-117, 1998.
DOI : 10.1016/S0020-0190(98)00104-5
URL : https://hal.archives-ouvertes.fr/hal-00619578
, Data compression using antidictionaries, Proceedings of the IEEE, vol.88, issue.11, pp.1756-1768, 2000.
DOI : 10.1109/5.892711
URL : https://hal.archives-ouvertes.fr/hal-00619579
, Optimal suffix tree construction with large alphabets, Proceedings 38th Annual Symposium on Foundations of Computer Science, pp.137-143, 1997.
DOI : 10.1109/SFCS.1997.646102
, Compressing and indexing labeled trees, with applications, Journal of the ACM, vol.57, issue.1, 2009.
DOI : 10.1145/1613676.1613680
URL : http://people.unipmn.it/manzini/papers/xbwt.pdf
, Opportunistic data structures with applications, Proceedings 41st Annual Symposium on Foundations of Computer Science, pp.390-398, 2000.
DOI : 10.1109/SFCS.2000.892127
, High-order entropy-compressed text indexes, SODA, pp.841-850, 2003.
DOI : 10.1007/978-3-642-40273-9_14
, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, Proceedings ACM Symposium on the Theory of Computing, pp.397-406, 2000.
DOI : 10.1137/S0097539702402354
, Algorithms on strings, trees and sequences: computer science and computational biology, 1997.
DOI : 10.1017/CBO9780511574931
, Fast Algorithms for Finding Nearest Common Ancestors, SIAM Journal on Computing, vol.13, issue.2, pp.338-355, 1984.
DOI : 10.1137/0213024
, Space-Efficient Framework for Top-k String Retrieval Problems, 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp.713-722, 2009.
DOI : 10.1109/FOCS.2009.19
, Color set size problem with applications to string matching, Proceedings of the 3rd Annual Symposium on Combinatorial Pattern Matching, number 644 in Lecture Notes in Computer Science, pp.230-243, 1992.
, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing , STOC '72, pp.125-136, 1972.
DOI : 10.1145/800152.804905
, Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications, In CPM, pp.181-192, 2001.
DOI : 10.1007/3-540-48194-X_17
URL : http://www.cs.iastate.edu/~cs548/references/linear_lcp.pdf
, Reducing the space requirement of suffix trees, Software: Practice and Experience, vol.15, issue.13, pp.1149-1171, 1999.
DOI : 10.1093/bioinformatics/15.5.426
URL : http://www.daimi.au.dk/~cstorm/courses/StrAlg_e07/papers/Kurtz1999_SuffixTrees.pdf
, String matching in erroneus input, 1986.
, On the Complexity of Finite Sequences, IEEE Transactions on Information Theory, vol.22, issue.1, pp.75-81, 1976.
DOI : 10.1109/TIT.1976.1055501
, Suffix Arrays: A New Method for On-Line String Searches, Proceedings of the 1st ACM-SIAM Annual Symposium on Discrete Algorithms, pp.319-327, 1990.
DOI : 10.1137/0222058
URL : http://webglimpse.net/pubs/suffix.pdf
, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM, vol.23, issue.2, pp.262-272, 1976.
DOI : 10.1145/321941.321946
, Efficient algorithms for document listing problems, Proceedings of the 13th ACM-SIAM Annual Symposium on Discrete Algorithms, pp.657-666, 2002.
, Two-Dimensional Pattern Indexing, Encyclopedia of Algorithms, 2008.
DOI : 10.1007/978-0-387-30162-4_442
, Two Efficient Algorithms for Linear Time Suffix Array Construction, IEEE Transactions on Computers, vol.60, issue.10, pp.1471-1484, 2011.
DOI : 10.1109/TC.2010.188
, The Gold-Bug and Other Tales. Dover Thrift Editions Series, 1991.
, Improvements and applications for the Weiner repetition finder, 1975.
, Linear Algorithm for Data Compression via String Matching, Journal of the ACM, vol.28, issue.1, pp.16-24, 1981.
DOI : 10.1145/322234.322237
, On-line construction of suffix trees, Algorithmica, vol.10, issue.3, pp.249-260, 1995.
DOI : 10.1145/321941.321946
URL : http://www.cs.helsinki.fi/u/ukkonen/SuffixT1.ps
, The Average Common Substring Approach to Phylogenomic Reconstruction, Journal of Computational Biology, vol.13, issue.2, pp.336-350, 2006.
DOI : 10.1089/cmb.2006.13.336
URL : http://www.cs.tau.ac.il/~bchor/ACS.pdf
, Linear pattern matching algorithms, 14th Annual Symposium on Switching and Automata Theory (swat 1973), pp.1-11, 1973.
DOI : 10.1109/SWAT.1973.13
URL : http://airelles.i3s.unice.fr/files/Weiner.pdf
, APPENDIX: TO KNOW MORE A preliminary version of this article associated with the special session celebrating the 40th anniversary of the appearance of Weiner's paper appeared as: A Forty years of text indexing The story of William Legrand is from: E. A. Poe: The Gold-Bug and Other Tales, Combinatorial Pattern Matching, number 7922 in LNCS, pp.1-10, 1991.
, The file transmission problem, Proceedings of the June 4-8, 1973, national computer conference and exposition on, AFIPS '73, 1973.
DOI : 10.1145/1499586.1499701
, Algorithms on strings, trees and sequences: computer science and computational biology: Algorithms on Strings Statistical characterizations of coding and promoter regions abound in the post-genome, starting with J. van Helden, B. André, and J. Collado-Vides: Extracting regulatory sites from the upstream region of the yeast genes by computational analysis of oligonucleotides For parallel constructions based on Karp-Miller-Rozenberg paradigm see: Z. Galil: Optimal parallel algorithms for string matching, Proceedings of the 16th ACM Symposium on the Theory of Computing, pp.827-842, 1984.
DOI : 10.1017/CBO9780511574931
, Galil: Optimal parallel algorithms for string matching, Z
, Parallel construction of a suffix tree with applications Rytter: Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays Partial attempts at online ST construction were contributed by M Time optimal left to right construction of position trees Efficient on-line construction and correction of position trees Further relationships among suffix trees and DAWGs are described by M. Crochemore in Reducing space for index implementation On-line construction of compact directed acyclic word graphs For Slissenko's work on string matching see A. O. Slisenko: Determination in real time of all the periodicities in a word Slisenko: Detection of periodicities and string matching in real time, Additional references on macro schemes can be found in J. A. Storer and T. G, pp.144-157347, 1965.
, Data compression via textual substitution An important step towards construction in secondary memory was achieved by P. Ferragina, R. Grossi: The String B-tree: a new data structure for string search in external memory and its applications The journal version of Suffix arrays appeared as U. Manber and G. Myers: Suffix arrays: a new method for on-line string searches The modifications to Farach's algorithm were proposed in J. Karkkainen and P. Sanders: Simple linear-work suffix array construction, Proceedings of the 10th ACM Symposium on the Theory of Computing Automata, Languages and Programming, 30th International Colloquium Proceedings, volume 2719 of Lecture Notes in Computer Science Suffix arrays in linear time are in D. K. Kim, J. S. Sim, H. Park, and K. Park: Constructing suffix arrays in linear time, pp.30-39928, 1978.
, See also P. Ko and S. Aluru: Space-efficient linear-time construction of suffix arrays, J. Discrete Algorithms J. Discrete Algorithms, vol.3, issue.32-4, pp.126-142143, 2005.
, Early work on approximate indexed searches includes E. Ukkonen: Approximate String-Matching over Suffix Trees Cobbs: Fast approximate matching using suffix trees The constant-time LCA solution was due to D Fast algorithms for finding nearest common ancestors A simpler implementation was proposed in M. A. Bender and M. Farach-Colton: The LCA problem revisited Axel Thue's landmark paper on square-free morphism is A. Thue: Uber die gegenseitige lage gleicher teile gewisser zeichenreichen Stoye: Linear-time algorithms for finding and representing all the tandem repeats in a string, Fast parallel and serial approximate string matching Proc. 6th Ann. Symp. on Combinatorial Pattern Matching (CPM'95) LATIN 2000: Theoretical Informatics, 4th Latin American Symposium Proceedings , volume 1776 of Lecture Notes in Computer Science, pp.157-169, 1912.
, For orthogonal range queries see M. Lewenstein: Orthogonal range searching for text indexing, Space-Efficient Data Structures, Streams, and Algorithms, pp.525-546, 2004.
, On-line construction of twodimensional suffix trees in O(n 2 log n) time. Algorithmica For applications of wavelet trees see P The myriad virtues of wavelet trees Suffix trees and their derivatives find countless applications in bioinformatics, more recently for the search of short strings produced by sequencing into massive genomes. For a couple of examples, see H. Li and R. Durbin: Fast and accurate long read alignment with Burrows-Wheeler Transform, Inf. Comput. Bioinformatics, vol.48, issue.26, pp.173-186849, 2007.
, How to map billions of short reads onto genomes, Proceedings of the Annual International Conference on on Computational Molecular Biology (RECOMB) ACM press, pp.455-457, 2002.
DOI : 10.1038/nbt0509-455