@TechReport{Maas03b,
author = {Moritz G. Maa{\ss}},
title = {A Fast Algorithm for the Inexact Characteristic String Problem},
institution = {Fakult{\"a}t f{\"u}r Informatik, TU M{\"u}nchen},
year = 2003,
month = {aug},
abstract = {We present a new algorithm to solve the {\scshape Inexact Characteristic String Problem} using
Hamming distance instead of Levenshtein distance as a
measure. We embed our new algorithm and the
previously known algorithm for Levenshtein distance in a
common framework which reveals an additional
improvement to the Levenshtein distance algorithm. The
{\scshape Inexact Characteristic String Problem} can
thus be solved in time $\mathcal{O}(||T|| +
l\cdot||S \setminus T||)$ for Hamming distance and in
time $\mathcal{O}(||T||+k\cdot{}l\cdot{}||S\setminus{}T||)$
forLevenshtein distance, where $S \subseteq \Sigma^*$, $T
\subset S$ ($T\neq\emptyset$) is the target set,
and $l$ is the length of a shortest string in $T$.
The {\scshape Inexact Characteristic String Problem} has applications in probe and primer
design.
Both algorithms need to solve the {\scshape Common Substring Problem} for more
than two strings. We present an improved algorithm
for this problem being simpler and faster in
practice by a constant factor than the previous
algorithm.},
number = {TUM-I0312},
url = {http://wwwbib.informatik.tu-muenchen.de/infberichte/2003/TUM-I0312.ps.gz}
}