Document Type

Report

Date

8-23-1989

Embargo Period

4-30-2012

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.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-89-12

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.