Edit distance for huge strings with bounds
You can use the usual dynamic programming algorithm. Instead of computing the edit distance between all prefixes of the input strings, compute only the edit distance between prefixes whose length is at most 100 apart. This reduces the number of entries to compute from $10^{14}$ to roughly $2\cdot 10^9$, which is feasible.