Advertisement
Published in:
2007 | OriginalPaper | Chapter
Self-normalised Distance with Don’t Cares
Authors : Peter Clifford, Raphaël Clifford
Published in: Combinatorial Pattern Matching
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present
O
(
n
log
m
) algorithms for a new class of problems termed
self-normalised distance with don’t cares
. The input is a pattern
p
of length
m
and text
t
of length
n
>
m
. The elements of these strings are either integers or wild card symbols. In the shift version, the problem is to compute
$\min_{\alpha}\sum_{j=0}^{m-1}(\alpha + p_j - t_{i+j})^2$
for all
i
, where wild cards do not contribute to the sum. In the shift-scale version, the objective is to compute
$\min_{\alpha,\beta}\sum_{j=0}^{m-1}(\alpha+ \beta p_j - t_{i+j})^2$
for all
i
, similarly. We show that the algorithms have the additional benefit of providing simple
O
(
n
log
m
) solutions for the problems of exact matching with don’t cares, exact shift matching with don’t cares and exact shift-scale matching with don’t cares.