类Levenshtein距离算法需求：将字符串修改为另一字符串最长子串

你的需求本质是在目标字符串s2的所有子串中，找到与输入字符串s1编辑距离最小且长度最长的子串T，最终返回将s1编辑为T后的结果，这是Levenshtein距离与最长公共子串问题的结合变种，已有成熟的解决思路。

核心思路 #

不同于标准Levenshtein距离计算“s1转成完整s2的最小编辑次数”，我们需要遍历s2的所有可能子串，计算每个子串与s1的Levenshtein距离，然后筛选出两个维度的最优解：

• 编辑距离最小
• 在距离相同的情况下，子串长度最长

最终返回的就是s1编辑为该最优子串后的结果（也就是该子串本身）。

示例验证 #

以你给出的例子：

• s1 = "stak"，s2 = "stackoverflow"
• s2的子串"stack"与s1的编辑距离为1（仅需在'a'和'k'之间添加'c'）
• 其他编辑距离为1的修改结果（如将'k'改为'e'得到"stae"）并非s2的子串；而同为s2子串的"sta"（编辑距离1，删除'k'）长度更短
• 因此"stack"是符合要求的最优结果

算法实现步骤 #

1. 构建动态规划表：
   创建二维数组dp[i][j]，其中dp[i][j]存储两个信息：

   • s1的前i个字符转换为s2中以第j个字符结尾的子串的最小编辑距离
   • 对应子串的起始位置（用于后续提取子串）

   状态转移逻辑参考标准Levenshtein距离：

   • 若s1[i-1] == s2[j-1]，则dp[i][j].distance = dp[i-1][j-1].distance，子串起始位置与dp[i-1][j-1]一致
   • 否则，dp[i][j].distance = min(dp[i-1][j].distance + 1, dp[i][j-1].distance + 1, dp[i-1][j-1].distance + 1)，并对应记录子串的起始位置

2. 筛选最优子串：
   遍历整个DP表，收集所有可能的子串对应的编辑距离和长度，筛选出编辑距离最小且长度最长的子串T。

3. 返回结果：
   直接返回子串T（因为这就是s1经过最少编辑后得到的、属于s2的最长子串）

应用场景 #

该算法可直接用于用户输入片段的补全与纠错：当用户输入不完整或拼写有误的字符串时，从目标文本库中匹配出最接近的最长有效子串，提供给用户正确的结果集。

内容的提问来源于stack exchange，提问作者Ming Hieu