|
Dist tables are key players in the computation of dynamic programming
tables in o(n2) time.
Given two strings A and T, dist(A,T)
stores the scores of the edit distances between T and all substrings
of A.
Given dist(A,T) and dist(B,T)
(strings A and B are each of length m and T
is of length n)
the best known algorithms that compute dist(AB,T)
run in O(nm) time or O(n1.5) time.
We will discuss the use of dist tables and Schmidt and Tiskin's Algorithms
as well as some thoughts on possible directions to answering the open problem.
|
