Juha K rkk inen, Esko Ukkonen Abstract. Using test strings read from the test points the algorithms eliminate as many potential occurrences of P as possible. The remaining potential occurrences are separately checked for actual occurrences. This is shown to be optimal by a generalization of a one-dimensional lower bound result by Yao.
Experimental results show that the algorithms are efficient in practice, too.
The method is also generalized for the k mismatches problem. The text processing can be done on-line, using a rather small window. The algorithms easily generalize to d -dimensional matching for any d . 68U10 PII .