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²/logn) to be an upper time bound on string matching. This result is tight by a previously known lower bound.