8

给定一个要匹配的字符串和一个模式，如何有效地找到零个或一个不匹配的匹配项。

e.g) 
S = abbbaaabbbabab
P = abab

Matches are abbb(index 0),aaab(index 4),abbb(index 6),abab(index 10)

我试图修改 KMP 算法，但我不确定该方法。

请给我一个想法来解决这个问题。

谢谢。

4

4 回答 4

5

好的，我找到了！我找到了最好的算法！

这听起来可能有点勇敢，但只要我要提出的算法同时具有运行时间O(m + n)和内存消耗O(m + n)，并且条目数据本身具有相同的属性，则该算法只能在常量中进行优化。

使用的算法

我将在我的解决方案中使用 KMP 和Rabin Karp算法之间的混合。Rabin Karp 使用滚动哈希来比较初始字符串的子字符串。它需要使用线性附加内存的线性时间预计算，但从那时起，两个字符串的子字符串之间的比较是恒定的O(1)（如果您正确处理冲突，这将摊销）。

我的解决方案不会做什么

我的解决方案不会在第一个字符串中找到与第二个字符串匹配的所有匹配项，最多相差 1 个。但是，可以修改算法，以便对于第一个字符串中的每个起始索引，如果存在这样的匹配，则至少会找到其中一个（这留给读者）。

观察

设m第二个字符串n的长度和 - 第一个字符串的长度。我将把任务分成两部分：如果我的目标是找到最多有一个差异的匹配，我想找到第一个字符串的子字符串：PREF将是单个差异之前的SUFF子字符串和之后的子字符串区别。我想要len(PREF) + len(SUFF) + 1 = m, where PREForSUFF将在需要时被人为缩短（当字符串匹配没有差异时）。

我将我的解决方案基于一个非常重要的观察：假设第一个字符串的子字符串从 index 开始，i其长度m与第二个字符串匹配，最多有一个差异。然后，如果我们PREF尽可能长时间地使用，仍然会有解决方案SUFF。这很明显：我只是尽可能地将差异推到最后。

算法

现在遵循算法本身。从通常的 KMP 开始。每次当前缀扩展失败并且要遵循失败链接时，首先检查是否跳过下一个字母剩余的后缀是否匹配第二个字符串的剩余部分。如果是这样，则找到最多具有一个字符差异的所寻求的匹配。如果不是 - 我们继续使用普通 KMP 进行 Rabin Karp 检查，每次要遵循失败链接。

让我用一个例子进一步澄清 Rabin Karp 检查。假设我们在 KMP 的某个步骤，我们发现first.substring[i, i + k - 1]匹配k第二个字符串的第一个字母。还假设该字母first[i + k]不同于second[k]。然后使用 Rabin Karp检查是否first.substring[i + k + 1, i + m - 1]完全匹配。second.substring[k + 1, m - 1]这正是您i尽可能地扩展了起始前缀形式索引并且您现在尝试是否存在最多一个差异的匹配的情况。

Rabin Karp 仅在跟随失败链接时使用，它将前缀的起始索引移动至少一个，这意味着最多O(n)使用 Rabin Karp 调用，每个调用都具有复杂度O(1)，总复杂度为线性复杂度。

于 2012-04-15T06:45:34.743 回答
2

这被称为近似字符串匹配问题。在您的特定情况下，您希望最大编辑距离为 1。

bitap算法是一种相当快速的解决方法。

于 2012-04-12T10:05:40.283 回答
2

要查找包括一个不匹配在内的所有子匹配，您需要 2 个 z 函数（一个用于原始 P，另一个用于反向 P）。在原始和反转字符串 S 的最长前缀子匹配的 buld 数组之后。稍后您需要反转第二个数组。最后一切都很简单：遍历第一个数组并检查最长前缀的长度是否等于 P 的长度。如果是，那么它是一个没有错误的匹配。如果它更短，则检查位置 (i + length(P) - 1) 处的第二个数组。如果两个值之和等于 length(P) - 1，则它是一个错误的子匹配。

复杂度为 O(len(P) + len(S))

于 2012-06-02T09:44:08.160 回答
1

Gonzalo Navarro 在他的近似字符串匹配指南中全面概述了各种算法以及它们如何相互比较。第 80、81 和 82 页显示了复杂性结果，包括最坏和平均情况，以及各种算法的空间要求。

（在此处使用的符号中，n 是指您搜索的文本的长度，m 是模式的长度，σ 是字母表的大小，k 是最大编辑距离，在您的情况下为 1。）

于 2012-04-13T01:48:39.400 回答