问确定字符串S中需要修改的最小字符数的算法

EN

显而易见的解决方案是在输入字符串S上移动参考词W，并计算差异。然而，对于非常长的字符串，这将变得效率低下。那么，我们如何改进这一点呢？

我们的想法是将搜索的目标定位在S中很可能与W匹配的地方。找到这些点是关键的部分。如果不执行朴素算法，我们就无法有效和准确地找到它们。因此，我们使用启发式H，它为我们必须执行的更改数量提供了一个下限。我们为S的每个位置计算这个下限。然后，我们从最低H的位置开始，检查该位置的S和W的实际差异。如果下一个更高的H高于当前的差值，我们已经完成了。如果不是，我们检查下一个位置。该算法的概要如下：

input:
    W of length LW
    S of length LS

H := list of length LS - LW + 1 with tuples [index, mincost]
for i from 0 to LS - LW
    H(i) = [i, calculate Heuristic for S[i .. i + LW]]
order H by mincost
actualcost = infinity
nextEntryInH = 0
while actualcost >= H[nextEntryInH].minCost && nextEntryInH < length(H)
    calculate actual cost for S[H[nextEntryInH].index .. + LW]
    update actualcost if we found a lesser cost or equal cost with an earlier difference
    nextEntryInH++

现在，回到启发式。我们需要找到一些东西，允许我们近似给定位置的差异(我们需要保证它是一个下限)，同时又易于计算。因为我们的字母表是有限的，所以我们可以使用字母的直方图来实现这一点。因此，让我们假设注释中的示例：W = worldcup，我们感兴趣的S部分是worstcap。这两个部分的直方图是(省略不出现的字母)：

         a c d l o p r s t u w
worldcup 0 1 1 1 1 1 1 0 0 1 1  
worstcap 1 1 0 0 1 1 1 1 1 0 1 
------------------------------
abs diff 1 0 1 1 0 0 0 1 1 1 0  (sum = 6)

我们可以看到，绝对差和的一半是我们需要更改的字母数的适当下限(因为每次字母更改都会使总和减少2)。在这种情况下，界限甚至很紧，因为总和等于实际成本。但是，我们的启发式算法没有考虑字母的顺序。但归根结底，这就是它可有效计算的原因。

好的，我们的启发式算法是直方图的绝对差值之和。现在，我们如何有效地计算它呢？幸运的是，我们可以递增地计算直方图和总和。我们从位置0开始计算完整的直方图和绝对差异的总和(请注意，在运行时的其余时间内，W的直方图永远不会改变)。有了这些信息，我们就可以设置H(0)了。

为了计算H的其余部分，我们在S上滑动窗口。当我们将窗口向右滑动一个字母时，我们只需要更新直方图并稍微求和:窗口中恰好有一个新字母(添加到直方图中)，一个字母离开窗口(从直方图中删除)。对于两个(或一个)对应的字母，计算绝对差异总和的结果变化并更新它。然后，相应地设置H。

使用这种方法，我们可以在线性时间内计算整个字符串S的启发式。启发式给我们一个指示，我们应该在哪里寻找匹配。一旦我们有了它，我们就继续执行这个答案开头概述的剩余算法(从启发式较低的地方开始精确的成本计算，并继续直到实际成本超过下一个更高的启发式值)。

LCS (=最长的公共子序列)将不起作用，因为W和S中的公共字母需要具有匹配的位置。因为您只允许更新，而不允许删除/插入。

如果允许移除/插入，则可以使用Levenshtein距离：https://en.wikipedia.org/wiki/Levenshtein_distance

在您的情况下，一个明显的强力解决方案是在每个位置将W与S匹配，复杂度为O (N *M) (S的N大小，W的M大小)