External inverse pattern matching

Leszek Antoni Gasieniec, Piotr Indyk, Piotr Krysta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


In this paper we consider the external inverse pattern matching problem. Given a text T of lengthn over an ordered alphabet Σ and a number m ≤ n, the goal is to find a pattern (formula presented)MAX ∈ Σm which is not a subword of T and which maximizes the sum of Hamming distances between (formula presented)MAX and all subwords of T of length m. We present an optimal O(n log σ)-time (where σ = ∣Σ∣) algorithm for the external inverse pattern matching problem. This substantially improves the O(nm log σ)-time algorithm given in [2]. Moreover we discuss briefly fast parallel implementation of our algorithm on the CREW PRAM model.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 8th Annual Symposium, CPM 1997, Proceedings
EditorsAlberto Apostolico, Alberto Apostolico, Jotun Hein
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540632207
StatePublished - 1997
Externally publishedYes
Event8th Annual Symposium on Combinatorial Pattern Matching, CPM 1997 - Aarhus, Denmark
Duration: Jun 30 1997Jul 2 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th Annual Symposium on Combinatorial Pattern Matching, CPM 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'External inverse pattern matching'. Together they form a unique fingerprint.

Cite this