Simple Optimal String Matching Algorithm (Extended Abstract)
Cyril Allauzen, Mathieu Raffinot · 2002
We present a new string matching algorithm linear in the worst case (in O(m + n )w heren is the size of the text and m the size of the searched word, both taken on an alphabet Σ )a nd opti- mal on average (with equiprobability and independence of letters, in O(m + n log|Σ| m/m)). Of all the algorithms that verify these two com- plexities, our 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 p1 ,t henp1p2 ,p 1p2p3 ,...,p 1p2p3 ...p i with O( |pi|) total preprocessing time. Among the algorithms that ver- ify this property (for instance the Knuth-Morris-Pratt) our algorithm is the only one to be optimal on average.