Luca's Project and Presentation in String Matching

Luca's Project and Presentation in String Matching

On Tuesday 19 March 2002, in classroom 13 N (ground floor of the new building), starting at 14:00 (2 p.m.), Luca Tabarelli will present the following classical string matching algorithms:

brute force
Rabin-Karp
Knuth-Morris-Pratt
Boyer-Moore

The problem addressed by the above algorithms is the following.
INPUT: Two strings: a string called Text and a string called Pattern
OUTPUT: The full list of the positions at which the occurrences of Pattern inside Text begin.
The same algorithms remain the state of the art even when one is intrested into the following output.
OUTPUT': The positions at which the first occurrences of Pattern inside Text begins, or NULL if Text contains no occurrence of Pattern.

More notions, references and details on the aspects touched upon in this talk can be found in

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L., Introduction to Algorithms, MIT Press, Cambridge, MA; McGraw-Hill Book Co., New York (1990) ISBN 0-262-03141-8

We expect that the talk of Luca will end at about 15:00 (3 p.m.). Just after Luca's talk, and in the same classroom, Marco Rospocher will practice a presentation of his thesis (to be discussed officially next week). The thesis is in Combinatorial Optimization. I am his advisor.

18-March-2002