On the size of Boyer–Moore automata

In this work we study the size of Boyer–Moore automata introduced in Knuth, Morris & Pratt’s famous paper on pattern matching. We experimentally show that a finite class of binary patterns produce very large Boyer–Moore automata, and find one particular case which we conjecture, generates automata of size Ω(m6). Further experimental results suggest that the maximal size could be a polynomial of O(m7), or even an exponential O(20.4m), where m is the length of the pattern.