The exact online string matching problem

✍ Scribed by Faro, Simone; Lecroq, Thierry

• Book ID: 121232296
• Publisher: Association for Computing Machinery
• Year: 2013
• Tongue: English
• Weight: 418 KB
• Volume: 45
• Category: Article
• ISSN: 0360-0300
• DOI: 10.1145/2431211.2431212

✦ Synopsis

This article addresses the
online exact string matching problem
which consists in finding
all
occurrences of a given pattern
p
in a text
t
. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry.

In the last decade more than 50 new algorithms have been proposed for the problem, which add up to a wide set of (almost 40) algorithms presented before 2000. In this article we review the string matching algorithms presented in the last decade and present experimental results in order to bring order among the dozens of articles published in this area.