de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

External inverse pattern matching

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44478

Gasieniec,  Leszek
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44676

Indyk,  Piotr
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44853

Krysta,  Piotr
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1996-1-030
(beliebiger Volltext), 10KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Gasieniec, L., Indyk, P., & Krysta, P.(1996). External inverse pattern matching (MPI-I-1996-1-030). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-A410-3
Zusammenfassung
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.