String matching with simple devices
With the help of a general simulation technique of deterministic finite two-way multi-head automata by automata with blind heads we show O(n(2)/logn) to be an upper time bound on string matching. This resultis tight by apreviously known lowerbound. (c) 2007 Elsevier B.V. All rights reserved.
string matching computational complexity theory of computation