在两个略有不同的字符串中找到相同的位置

Question

我有两个字符串，第一个是主字符串，第二个是从字符串。它们都包含相似的值，除了奴隶将添加或删除字符。

我需要找到字符从偏移主的字符串从为每个字符串主字符串。

我目前正在使用百分比作为在从属字符串中查找类似偏移量的算法。

例如;

const master = 'The chicken is blue, but not really a chicken';

const slave = 'This large bird is blue, but is really a dog';

function slaveOffset(m, offset, s): number {

    return Math.floor(s.length * (offset / m.length));

}

console.log(slaveOffset(master, 15, slave)); // prints 12

当从主站翻译位置 15（读作“鸡是”）时，从站位置计算为 12。读作“这个大 b”，因为使用百分比根本不准确（不考虑添加或删除字符）。

正确的值应该是 18（读作“大鸟是”），因为主偏移量以“是”结束。

我需要一个算法slaveOffset()来处理添加和删除的字符并找到最可能的从偏移量。它不需要过于准确，但应该解决由于字符变化引起的大偏差问题。

Answer 1

这是计算机科学中的一个经典问题，通常称为“数据比较”或简称为“差异”。最常见的算法应用最长公共子序列技术，但在一般情况下，这是一个 NP-hard 问题，因此应用各种启发式方法来获得“足够好”的结果，通常由循环中的人进行调整。查找一些diff算法以获得一些想法。在您的情况下，您可能希望从“从属字符串从哪里开始与主字符串不同以及从哪里再次变得相同”的启发式开始。字符串匹配前两个字符，但下一次获得超过 3 个字符的匹配序列时，将出现在字符,i和 处s。这些点成为您可以在slaveOffset函数中使用的标记。