Skip to Main content Skip to Navigation
Journal articles

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
Contributor : Mathieu Raffinot <>
Submitted on : Wednesday, May 2, 2012 - 11:26:18 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM




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⟩



Record views