algorithm - 在另一个字符串中找到最大相似子串

Question

我得到了两个字符串，n1 和 n2。除了这些，我还得到了一个数字 K。

现在我需要找到三个数字 - i,j,l 使得: n1 中从索引 i 开始的长度为 l 的子串与 n2 中索引为 j 的长度为 l 的子串最多有 K 个不匹配。这是 K 相异度可能的最大子串。

一个例子应该很清楚:
n1 = 大不里士
n2 =都灵
K = 2
那么输出应该是:
我 = 2
j = 1
l = 4
[因为“briz”和“orin”有两个不同点]

当前方法:对于 n1 的每个子序列，我试图找到 n2 中的最大公共(public)子序列(最多有 K 个不匹配)。有人有更好的方法来更有效地解决这个问题吗？

Answer 1

这是一个简单的暴力破解。它计算每对可能的 i 和 j 的长度。复杂度为 O(n1.length * n2.length * min(n1.length, n2.length))。当两个字符串的长度都是 n 时，这是 O(n³)。

for (i = 0; i < n1.length; i++)
{
    for (j = 0; j < n2.length; j++)
    {
        errors = 0
        len = 0

        while (errors <= k && i+len < n1.length && j+len < n2.length)
        {
             if (n1[i+len] != n2[j+len]) errors++
             if (errors <= k) len++
        }

        if (len > best) update best
    }
}

这是一个更有效的解决方案，它遍历 i 和 j 之间所有可能的偏移量，在该偏移量处设置一个有 k 个错误的子串，然后移动子串(使其恰好有 k 个错误)并观察每个点的长度。复杂度为 O((n1.length + n2.length) * min(n1.length, n2.length))。当两个字符串的长度都是 n 时，这是 O(n²)。

for (offset = -n1.length; offset < n2.length; offset++)
{
    // j is equal to (i + offset)

    start = (offset > 0) ? 0 : -offset
    stop = min(n1.length, n2.length - offset)

    errors = 0
    e = start // e is one past the end of the sequence, so l = e - i

    for (i = start; i < stop; i++)
    {
        // move the end of the substring to maintain exactly k errors
        while (e < stop && (errors < k || n1[e] == n2[e+offset]))
        {
            if (n1[e] != n2[e+offset]) errors++
            e++
        }

        if (e - i > best) update best

        if (n1[i] != n2[i+offset]) errors--
    }
}