非表示:
キーワード:
-
要旨:
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.
