We then explore other novel techniques to cope with longer patterns. We show how to partition the pattern into short subpatterns which can be searched with less errors using the simple automaton, to obtain an average cost close to O ( sqrt (mk/w) n). Moreover, we allow to superimpose many subpatterns in a single automaton, obtaining near O ( sqrt (mk/(sigma w))m n) average complexity (sigma is the alphabet size).
We perform a complete analysis of all the techniques and show how to combine them in an optimal form, obtaining also new tighter bounds for the probability of an approximate occurrence in random text. Finally, we show experimental results comparing our algorithms against previous work. Those experiments show that our algorithms are among the fastest ones for typical text searching, being the fastest in some cases. Although we aim mainly to text searching, we believe that our ideas can be successfully applied to other areas such as computational biology.