我的输入是三个数字 - 一个数字s以及一个范围的开头b和结尾.任务是找到范围内的最小Levenstein距离和范围内的所有数字.没有必要找到最小化距离的数字,最小距离就足够了.e0 <= s,b,e <= 10^1000s[b, e]
显然我必须将数字作为字符串读取,因为标准C++类型不会处理如此大的数字.计算可能在很大范围内的每个数字的Levenstein距离是不可行的.
有任何想法吗？
[编辑 10/8/2013：DP 算法中考虑的某些情况实际上根本不需要考虑，尽管考虑它们不会导致不正确:)]
下面我将描述一个需要 O(N^2) 时间的算法，其中 N 是b、e 或 s 中的最大位数。由于所有这些数字都限制为 1000 位，这意味着最多需要几百万次基本操作，这在任何现代 CPU 上都需要几毫秒。
假设 s 有 n 位数字。下文中，“之间”表示“包括”；如果我的意思是“排除其端点”，我会说“严格介于”。索引从 1 开始。x[i] 表示 x 的第 i 个数字，因此例如 x[1] 是它的第一个数字。
首先要做的是将问题分解为一系列子问题，其中每个 b 和 e 具有相同的位数。假设 e 比 s 多 k >= 0 位：将问题分解为 k+1 个子问题。例如，如果 b = 5 且 e = 14032，则创建以下子问题：
我们可以解决每个子问题，并采取最小解决方案。
最简单的情况是中间的情况。每当 e 比 b 多 k >= 1 位数字时，就会出现 k-1 个子问题（例如上面的 3），其中 b 是 10 的幂，e 是 10 的下一个幂减 1。假设 b 是 10^m 。请注意，选择 1 到 9 之间的任何数字，后跟 0 到 9 之间的任何 m 个数字，将生成一个范围为 b <= x <= e 的数字 x。此外，在这个范围内没有任何数字不能通过这种方式产生。s（或者实际上任何不以 0 开头的给定长度 n 数字字符串）与10^m <= x <= 10^(m+1)-1 范围内的任何数字 x之间的最小编辑距离必然是abs(m+1-n)，因为如果m+1 >= n，可以简单地选择x的前n位与s中的相同，并删除其余部分，并且如果m+1 < n 然后选择前 m+1 与 s 中的相同，并将余数插入。
事实上，我们可以在单个常量时间操作中处理所有这些子问题：如果最小的“简单”子问题有 b = 10^m，最大的“简单”子问题有 b = 10^u，那么之间的最小编辑距离s 以及任何这些范围内的任何数字，如果 n < m，则为 mn，如果 n > u，则为 nu，否则为 0。
困难情况是 b 和 e 不限于分别具有 b = 10^m 和 e = 10^(m+1)-1 的形式。任何主问题最多可以生成两个子问题，如下所示：两个“端”（由 b 和 e 具有不同位数的主问题产生，如顶部的示例）或单个子问题（即主问题）问题本身，根本不需要细分，因为 b 和 e 已经具有相同的位数）。请注意，由于之前对问题进行了拆分，我们可以假设子问题的 b 和 e 具有相同的位数，我们将其称为 m。
我们要做的是设计 Levenshtein DP 矩阵的变体，用于计算给定数字字符串 (s) 与b <= x <= e 范围内的任何数字 x之间的最小编辑距离。尽管增加了“能力”，该算法仍将在 O(n^2) 时间内运行:)
首先，观察如果 b 和 e 具有相同的位数，并且 b != e，那么它们一定是由左侧的一些 q >= 0 个相同数字组成，后跟一个更大的数字e 中的值大于 b 中的值。现在考虑以下生成随机数字字符串 x 的过程：
基本思想是，在包含必须包含的所有数字后，您可以根据需要“拥抱”下界的数字，或者根据需要“拥抱”上限的数字，并且尽快当您决定停止“拥抱”时，您可以选择任何您想要的数字。对于合适的随机选择，此过程将生成所有且仅生成满足 b <= x <= e 的数字 x。
在长度分别为 n 和 m 的两个字符串 s 和 x 之间的“通常”编辑距离计算中，我们有一个从 (0, 0) 到 (n, m) 的矩形网格，并且在每个网格点 (i, j)我们记录前缀 s[1..i] 和前缀 x[1..j] 之间的编辑距离。(i, j) 处的分数是使用自下而上动态规划根据 (i-1, j)、(i, j-1) 和 (i-1, j-1) 处的分数计算得出的。为了适应这一点，将 x 视为一组可能的字符串（具体来说，对应于 b 和 e 之间的数字的数字字符串）而不是特定的给定字符串，我们需要做的是为每个字符串记录两个而不是一个分数网格点：一种情况是我们假设位置 j 处的数字被选择为接近下界，另一种情况是我们假设它被选择为接近上限。第三种可能性（上面的步骤 5）实际上不需要 DP 矩阵中的空间，因为我们可以立即计算出输入字符串的整个其余部分的最小编辑距离，这与我们计算“简单”的方式非常相似。 ”第一部分中的子问题。
称网格点 (i, j) 处的总体最小得分为 v(i, j)。如果字符 a 和 b 不同，则令 diff(a, b) = 1，否则为 0。如果字符 a 在 b..c 范围内，则令 inrange(a, b..c) 为 1，否则为 0。计算结果为：
# The best Lev distance overall between s[1..i] and x[1..j]
v(i, j) = min(hb(i, j), he(i, j))
# The best Lev distance between s[1..i] and x[1..j] obtainable by
# continuing to hug the lower bound
hb(i, j) = min(hb(i-1, j)+1, hb(i, j-1)+1, hb(i-1, j-1)+diff(s[i], b[j]))
# The best Lev distance between s[1..i] and x[1..j] obtainable by
# continuing to hug the upper bound
he(i, j) = min(he(i-1, j)+1, he(i, j-1)+1, he(i-1, j-1)+diff(s[i], e[j]))
在计算 v(i, j) 的时间点，我们还将计算选择“停止拥抱”所产生的编辑距离，即选择严格位于 b[j] 和 e[j 之间的数字] (if j == q) 或 (if j != q) 要么高于 b[j]，要么低于 e[j]，然后自由选择数字，使 x 的后缀与 s 的后缀尽可能匹配:
# The best Lev distance possible between the ENTIRE STRINGS s and x, given that
# we choose to stop hugging at the jth digit of x, and have optimally aligned
# the first i digits of s to these j digits
sh(i, j) = if j >= q then shc(i, j)+abs(n-i-m+j)
else infinity
shc(i, j) = if j == q then
min(hb(i, j-1)+1, hb(i-1, j-1)+inrange(s[i], (b[j]+1)..(e[j]-1)))
else
min(hb(i, j-1)+1, hb(i-1, j-1)+inrange(s[i], (b[j]+1)..9),
he(i, j-1)+1, he(i-1, j-1)+inrange(s[i], (0..(e[j]-1)))
shc(i, j) 的公式不需要考虑“向下”移动，因为此类移动不涉及 x 的任何数字选择。
对于所有 0 <= i <= n 和 0 <= j <= m，总体最小编辑距离是 v(n, m) 和 sh(i, j) 中的最小值。
取 N 为 s、b 或 e 中任意一个中最大的位数。使用 super-Levenshtein 算法，可以在线性时间内将原始问题分为最多 1 组简单问题（总共需要 O(1) 时间来解决）和 2 个困难子问题（每个问题需要 O(N^2) 时间来解决），所以总的来说，这个问题可以在 O(N^2) 时间内解决，即时间与位数的平方成正比。