SEVENTH INTERNATIONAL COLLOQUIUM ON NUMERICAL ANALYSIS AND COMPUTER
SCIENCE WITH APPLICATIONS
Plovdiv, Bulgaria, August 13-17, 1998
Abstract
Theoretical and practical aspects of string matching
Thierry Lecroq
e-mail:
Thierry.Lecroq@laposte.net
String matching is the problem of finding one or more generally all
the occurrences of a pattern in a text.
It principallly occurs in fields such as information retrieval,
bibliographic search and it has also some applications in molecular
biology.
We are interested here in the problem where the pattern in given first
and is searched is various texts.
A preprocessing phase is then possible on the pattern but not on the
text.
Many solutions for this problem have been devised.
We will present the family of algorithms derived from the famous
Boyer-Moore algorithm.
These algorithms have two main features: they have a linear theoretical
worst case and they perform very well in practice.
home page
Thierry Lecroq