Dist tables are key players in the computation of dynamic programming
tables in o(n^{2}) 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(n^{1.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.
