(the two previous algorithms are analyzed in Lecroq, and the algorithm of Colussi ((Colussi, 1992. ,
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 ,
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 ,
Algorithms for nding patterns in strings, Handbook of Theoretical Computer Science, pp.255-300, 1990. ,
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
Computer algorithms { Introduction to design and analysis, 1988. ,
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
A fast string searching algorithm, Communications of the ACM, vol.20, issue.10, pp.762-772, 1977. ,
DOI : 10.1145/359842.359859
Efficient Comparison Based String Matching, Journal of Complexity, vol.9, issue.3, pp.339-365, 1993. ,
DOI : 10.1006/jcom.1993.1022
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
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
Fastest Pattern Matching in Strings, Journal of Algorithms, vol.16, issue.2, pp.163-189, 1994. ,
DOI : 10.1006/jagm.1994.1008
Introduction to algorithms, 1990. ,
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
Text Algorithms, 1994. ,
URL : https://hal.archives-ouvertes.fr/hal-00619796
String Matching in Real Time, Journal of the ACM, vol.28, issue.1, pp.134-149, 1981. ,
DOI : 10.1145/322234.322244
On the Exact Complexity of String Matching: Upper Bounds, SIAM Journal on Computing, vol.21, issue.3, 1992. ,
DOI : 10.1137/0221028
Handbook of algorithms and data structures, 1991. ,
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
Practical fast searching in strings. Software { Practice and Experience, pp.501-506, 1980. ,
Fast string searching. Software { Practice and Experience, pp.1221-1248, 1991. ,
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=10.1.1.86.9502
Fast Pattern Matching in Strings, SIAM Journal on Computing, vol.6, issue.2, pp.323-350, 1977. ,
DOI : 10.1137/0206024
Experimental results on string-matching algorithms. Software { Practice and Experience, pp.727-765, 1995. ,
A space-economical suux tree construction algorithm, J. Algorithms, vol.23, pp.262-272, 1976. ,
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
String matching algorithms and automata, First American Workshop on String Processing, pp.151-157, 1993. ,
DOI : 10.1007/3-540-58131-6_61
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. ,