Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-96-1-030

External inverse pattern matching

Gasieniec, Leszek and Indyk, Piotr and Krysta, Piotr

MPI-I-96-1-030. November 1996, 12 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-96-1-030.ps158 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1996-1-030
Hide details for BibTeXBibTeX
@TECHREPORT{GasieniecIndykKrysta96,
  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},
}