2

可能重复：
确定数组是否包含 n…n+m 的算法？

让我们假设 M > N，并且您有 2 个数组。长度为 M 的一个称为 A，长度为 N 的一个称为 B。有没有更快的方法来确定数组 B 是否存在于数组 A 中？

例如：

A = [ 1 2 3 4 5 6 ]

B1 = [ 2 3 4 ]

因此数组 B1 存在于 A 中，而 [ 1 3 2 ] 之类的则不存在。

这本质上是在 Java 中使用 char 数组实现类似 isSubstring() 的东西。

我能想到的唯一方法是在 O(n^2) 中将 A 中的每个元素与 B 中的初始元素进行比较，然后遍历 B 以寻找匹配项。

我想这个问题在面试中相当普遍，所以我的问题是问是否有更快的方法。

4

1 回答 1

2

你想要KMP

algorithm kmp_search: 输入：一个字符数组，S（要搜索的文本）一个字符数组，W（搜索的词） 输出：一个整数（在 S 中找到 W 的从零开始的位置）

define variables:
    an integer, m ← 0 (the beginning of the current match in S)
    an integer, i ← 0 (the position of the current character in W)
    an array of integers, T (the table, computed elsewhere)

while m+i is less than the length of S, do:
    if W[i] = S[m + i],
        if i equals the (length of W)-1,
            return m
        let i ← i + 1
    otherwise,
        let m ← m + i - T[i],
        if T[i] is greater than -1,
            let i ← T[i]
        else
            let i ← 0

(if we reach here, we have searched all of S unsuccessfully)
return the length of S

复杂：

假设表 T 的先验存在，Knuth-Morris-Pratt 算法的搜索部分的复杂度为 O(k)，其中 k 是 S 的长度，O 是大 O 表示法。由于除了进入和退出函数的固定开销外，所有的计算都在while循环中进行，我们将计算这个循环的迭代次数的界限；为了做到这一点，我们首先对 T 的性质进行关键观察。根据定义，它的构造使得如果在 S[m + i] 与 W[i] 比较时从 S[m] 开始的匹配失败，那么下一个可能的匹配必须从 S[m + (i - T[i])] 开始。特别是下一个可能的匹配必须出现在比 m 更高的索引处，因此 T[i] < i。利用这个事实，我们将证明循环最多可以执行 2k 次。对于每次迭代，它执行循环中的两个分支之一。第一个分支总是增加 i 而不会改变 m，因此 S 的当前审查字符的索引 m + i 增加。第二个分支将 i - T[i] 添加到 m，正如我们所见，这始终是一个正数。因此增加了当前潜在匹配开始的位置m。现在，如果 m + i = k 则循环结束；因此，循环的每个分支最多可以到达 k 次，因为它们分别增加 m + i 或 m，并且 m ≤ m + i：如果 m = k，则肯定 m + i ≥ k，所以因为它增加最多以单位增量计算，我们必须在过去的某个时间点有 m + i = k，因此无论哪种方式我们都可以完成。因此循环最多执行 2k 次，表明搜索算法的时间复杂度为 O(k)。

附加信息：

KMP算法的效率

由于算法的两个部分分别具有 O(k) 和 O(n) 的复杂度，因此整个算法的复杂度为 O(n + k)。无论 W 或 S 中有多少重复模式，这些复杂性都是相同的。

于 2013-02-02T21:10:47.630 回答