The Center for Education and Research in Information Assurance and Security (CERIAS)

The Center for Education and Research in
Information Assurance and Security (CERIAS)
Center for Education and Research in Information Assurance and Security

A Randomized O(N Log N) Algorithm for Generalized Pattern Matching

Author

Mikhail J. Atallah, Frederic Chyzak, and Phillipe Dumas

Tech report number

CSD-TR-96-059

Entry type

techreport

Abstract

We give a randomized O(N Log M) time algorithm for determining the Hamming-distance score vector between a text string T of length N and a pattern string P of length M M <= N. This is the vector whose ith entry contains the number of positions at which there is equality between the symbols of the pattern and the corresponding positions of the substring that begins at the i-th position of the text. No assumptions are made about the size of the alphabet or about the probabilistic characteristics of the input. The solution extends to the weighted case, and to higher dimensions.

Date

1996

Institution

Department of Computer Science

Key alpha

atallah

School

Purdue University

Publication Date

0000-00-00

Location

A hard-copy of this is in the CERIAS Library

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.