@inproceedings{5373e20eb69645658bf3957169fc96b8,
title = "External inverse pattern matching",
abstract = "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.",
author = "Leszek G{\c a}sieniec and Piotr Indyk and Piotr Krysta",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 8th Annual Symposium on Combinatorial Pattern Matching, CPM 1997 ; Conference date: 30-06-1997 Through 02-07-1997",
year = "1997",
doi = "10.1007/3-540-63220-4_53",
language = "English (US)",
isbn = "9783540632207",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "90--101",
editor = "Alberto Apostolico and Alberto Apostolico and Jotun Hein",
booktitle = "Combinatorial Pattern Matching - 8th Annual Symposium, CPM 1997, Proceedings",
}