Jeudi 28 mars 2024, 14:00 à 15:00

Salle de séminaire du département informatique

Francesco Pio Marino

(Université de Catane et LITIS, Université de Rouen)

Sampled string matching is an efficient approach to the string matching problem introduced in order to overcome the prohibitive space requirements of indexed matching, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. Known solutions to sampled string matching are very efficient in practical cases being able to improve standard exact string matching algorithms up to 70% using less than  1% of the original text size.
Recently new methods have been introduced in order to solve approximate string matching such as the order preserving pattern matching problem, Cartesian-tree pattern matching or shape preserving pattern matching.