Simple optimal string matching algorithm

Abstract : We present a new string matching algorithm optimal on average (with equiprobability and independence of letters, in O(m + n log(\Sigma\) m/m), where n is the size of the text and m the size of the starched word, both taken on an alphabet Sigma) 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(Sigma\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. (C) 2000 Academic Press.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00693770
Contributor : Mathieu Raffinot <>
Submitted on : Wednesday, May 2, 2012 - 11:26:18 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM

Links full text

Identifiers

Collections

Citation

Cyril Allauzen, Mathieu Raffinot. Simple optimal string matching algorithm. Journal of Algorithms in Cognition, Informatics and Logic, Elsevier, 2000, 36 (1), pp.102--116. ⟨10.1006/jagm.2000.1087⟩. ⟨hal-00693770⟩

Share

Metrics

Record views

214