SEVENTH INTERNATIONAL COLLOQUIUM ON NUMERICAL ANALYSIS AND COMPUTER
SCIENCE WITH APPLICATIONS
Plovdiv, Bulgaria, August 13-17, 1998
Theoretical and practical aspects of string matching
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
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
Many solutions for this problem have been devised.
We will present the family of algorithms derived from the famous
These algorithms have two main features: they have a linear theoretical
worst case and they perform very well in practice.