. Crochemore, (the two previous algorithms are analyzed in Lecroq, and the algorithm of Colussi ((Colussi, 1992.

. Preex, A string v is a preex of a string u if u = vu 00 for some string u 00 . Proper: Qualiies a factor of a string that is not equal to the string itself

. Suux, A string v is a suux of a string u if u = u 0 v for some string u 0 . Suux tree: Trie containing all the suuxes of a string

A. V. Aho, Algorithms for nding patterns in strings, Handbook of Theoretical Computer Science, pp.255-300, 1990.

A. V. Aho and M. J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, vol.18, issue.6, pp.333-340, 1975.
DOI : 10.1145/360825.360855

S. Baase, Computer algorithms { Introduction to design and analysis, 1988.

A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, M. T. Chen et al., The smallest automation recognizing the subwords of a text, Theoretical Computer Science, vol.40, pp.31-55, 1985.
DOI : 10.1016/0304-3975(85)90157-4

R. S. Boyer and J. S. Moore, A fast string searching algorithm, Communications of the ACM, vol.20, issue.10, pp.762-772, 1977.
DOI : 10.1145/359842.359859

D. Breslauer and Z. Galil, Efficient Comparison Based String Matching, Journal of Complexity, vol.9, issue.3, pp.339-365, 1993.
DOI : 10.1006/jcom.1993.1022

R. Cole, Tight Bounds on the Complexity of the Boyer???Moore String Matching Algorithm, SIAM Journal on Computing, vol.23, issue.5, pp.1075-1091, 1994.
DOI : 10.1137/S0097539791195543

R. Cole, R. Hariharan, U. Zwick, and M. S. Paterson, Tighter Lower Bounds on the Exact Complexity of String Matching, SIAM Journal on Computing, vol.24, issue.1, pp.30-45, 1995.
DOI : 10.1137/S0097539793245829

L. Colussi, Fastest Pattern Matching in Strings, Journal of Algorithms, vol.16, issue.2, pp.163-189, 1994.
DOI : 10.1006/jagm.1994.1008

T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to algorithms, 1990.

M. Crochemore, Transducers and repetitions, Theoretical Computer Science, vol.45, pp.63-86, 1986.
DOI : 10.1016/0304-3975(86)90041-1

URL : https://hal.archives-ouvertes.fr/hal-00619540

M. Crochemore and W. Rytter, Text Algorithms, 1994.
URL : https://hal.archives-ouvertes.fr/hal-00619796

Z. Galil, String Matching in Real Time, Journal of the ACM, vol.28, issue.1, pp.134-149, 1981.
DOI : 10.1145/322234.322244

Z. Galil and R. Giancarlo, On the Exact Complexity of String Matching: Upper Bounds, SIAM Journal on Computing, vol.21, issue.3, 1992.
DOI : 10.1137/0221028

G. H. Gonnet and R. A. Baeza-yates, Handbook of algorithms and data structures, 1991.

C. Hancart, On Simon's string searching algorithm, Information Processing Letters, vol.47, issue.2, pp.95-99, 1993.
DOI : 10.1016/0020-0190(93)90231-W

R. N. Horspool, Practical fast searching in strings. Software { Practice and Experience, pp.501-506, 1980.

A. Hume and D. M. Sunday, Fast string searching. Software { Practice and Experience, pp.1221-1248, 1991.

R. M. Karp and M. O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, vol.31, issue.2, pp.249-260, 1987.
DOI : 10.1147/rd.312.0249

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

D. E. Knuth, M. Jr, J. H. Pratt, and V. R. , Fast Pattern Matching in Strings, SIAM Journal on Computing, vol.6, issue.2, pp.323-350, 1977.
DOI : 10.1137/0206024

T. Lecroq, Experimental results on string-matching algorithms. Software { Practice and Experience, pp.727-765, 1995.

E. M. Mccreight, A space-economical suux tree construction algorithm, J. Algorithms, vol.23, pp.262-272, 1976.

U. Manber and G. Myers, Suffix Arrays: A New Method for On-Line String Searches, SIAM Journal on Computing, vol.22, issue.5, pp.935-948, 1993.
DOI : 10.1137/0222058

I. Simon, String matching algorithms and automata, First American Workshop on String Processing, pp.151-157, 1993.
DOI : 10.1007/3-540-58131-6_61

G. A. Stephen, String searching algorithms 7 Further Information Problems and algorithms presented in the chapter are just a sample of questions related to pattern matching. They share the formal methods used to design eecient algorithms. A wider panorama of algorithms on texts may be found in a few books such as Crochemore and Rytter Research papers in pattern matching are disseminated in a few journals, among which are, Algorithmica. Two main annual conferences present the latest advances of this eld of research: Combinatorial Pattern Matching, which started and was held since in London (England) Asilomar (California), Helsinki (Finland), 1990.