  We study edit distance computation with preprocessing: the preprocessing
algorithm acts on each string separately, and then the query algorithm takes as
input the two preprocessed strings. This model is inspired by scenarios where
we would like to compute edit distance between many pairs in the same pool of
strings.
  Our results include:
  Permutation-LCS: If the LCS between two permutations has length $n-k$, we can
compute it \textit{ exactly} with $O(n \log(n))$ preprocessing and $O(k
\log(n))$ query time.
  Small edit distance: For general strings, if their edit distance is at most
$k$, we can compute it \textit{ exactly} with $O(n\log(n))$ preprocessing and
$O(k^2 \log(n))$ query time.
  Approximate edit distance: For the most general input, we can approximate the
edit distance to within factor $(7+o(1))$ with preprocessing time
$\tilde{O}(n^2)$ and query time $\tilde{O}(n^{1.5+o(1)})$.
  All of these results significantly improve over the state of the art in edit
distance computation without preprocessing. Interestingly, by combining ideas
from our algorithms with preprocessing, we provide new improved results for
approximating edit distance without preprocessing in subquadratic time.
