Simple Optimal String Matching Algorithm

✍ Scribed by Cyril Allauzen; Mathieu Raffinot

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 140 KB
• Volume: 36
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1087

✦ Synopsis

We present a new string matching algorithm optimal on average (with equiprobability and independence of letters, in O m + n log m/m , where n is the size of the text and m the size of the searched word, both taken on an alphabet ) and linear in the worst case (in O m + n ). Of all the algorithms that verify these two complexities, ours is the simplest since it uses only a single structure, a suffix automaton. Moreover, its preprocessing phase is linearly dynamical; i.e., it is possible to search the words p 1 , then p 1 p 2 p 1 p 2 p 3 p 1 p 2 p 3 p i with O p i total preprocessing time. Among the algorithms that verify this property (for instance, the Knuth-Morris-Pratt algorithm) our algorithm is the only one to be optimal on average.