Document Type
Report
Date
8-23-1989
Keywords
Pattern matching
Language
English
Disciplines
Computer Sciences
Description/Abstract
We give an algorithm which finds all occurrences of an m1 x m2 pattern array embedded as subarrays in an n1 x n2 array of text, where at most k mismatches are allowed per occurrence. The algorithm runs in time O((k+a)(blogb+ n1n2)), where a = min(m1m2) and b=max(m1m2). This improves upon the previously best known algorithm, and is asymptotically optimal for k ≈ a.
Recommended Citation
Ranka, Sanjay and Heywood, Todd, "Two-Dimensional Pattern Matching with k Mismatches" (1989). Electrical Engineering and Computer Science - Technical Reports. 62.
https://surface.syr.edu/eecs_techreports/62
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-89-12