MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


External inverse pattern matching

Gasieniec, Leszek and Indyk, Piotr and Krysta, Piotr

November 1996, 12 pages.

Status: available - back from printing

We consider {\sl external inverse pattern matching} problem. Given a text $\t$ of length $n$ over an ordered alphabet $\Sigma$, such that $|\Sigma|=\sigma$, and a number $m\le n$. The entire problem is to find a pattern $\pe\in \Sigma^m$ which is not a subword of $\t$ and which maximizes the sum of Hamming distances between $\pe$ and all subwords of $\t$ of length $m$. We present optimal $O(n\log\sigma)$-time algorithm for the external inverse pattern matching problem which substantially improves the only known polynomial $O(nm\log\sigma)$-time algorithm introduced by Amir, Apostolico and Lewenstein. Moreover we discuss a fast parallel implementation of our algorithm on the CREW PRAM model.

  • Attachement: (158 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Gasieniec, Leszek and Indyk, Piotr and Krysta, Piotr},
  TITLE = {External inverse pattern matching},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-96-1-030},
  MONTH = {November},
  YEAR = {1996},
  ISSN = {0946-011X},