1

我现在要道歉，因为这个问题在我脑海中听起来很愚蠢，而且我可能忽略了一些非常明显的事情。反正...

好的，所以我正在自学 scala，作为学习练习，我决定实现一种方法来确定一个字符串是否包含另一个更小的字符串。我做的第一件事是使用原始版本，在该版本中，我转到字符串的每个字母并开始向前检查以查看每个字符是否匹配。一切顺利。然后我决定实现一个更有效的方法，这就是我想出的（不包括特殊情况）：

// return true if a is a substring of b
def is_sub(a: String, b: String) : Boolean = {
  for(i <- 0 until b.length-a.length) { // O(n-m)
    if(a.hashCode == b.substring(i,a.length+i).hashCode) return true // O(1) + O(1) + O(1)
  }
  return false
}

首先，有人可以检查我的工作并确保我是对的。我容易犯愚蠢的错误。其次，您能否检查以确保我的时间复杂度是准确的。假设前 2 个是我认为的，为什么在 wikipedia 页面上没有提到字符串搜索算法的这种方法？理论上，这应该是 O(nm)，不需要预处理空间。

我在哪里搞砸了我对这个问题的分析？

4

2 回答 2

4

不保证您发布的代码是正确的。如果两个字符串相等，那么它们的哈希码一定是相同的，但反过来不一定成立。可以找到不同字符串但具有相同哈希码的字符串对。因此，如果您找到与要搜索的字符串具有相同哈希码的子字符串，您的函数可能会返回错误的答案。

此外，您的复杂性分析有点不正确。计算长度为 k 的字符串的哈希码需要时间 O(k)（假设您有一个不错的哈希函数！），所以这意味着在循环的每次迭代中，您将做 O(n) 的工作计算您采用的子字符串的哈希码。由于您执行此操作 O(m) 次，因此总时间复杂度为 O(mn)，而不是 O(m - n)。

但是，您所做的与Rabin-Karp 字符串搜索算法密切相关，该算法确实基于散列​​字符串。为了避免在每次迭代中做 O(n) 工作，该算法使用滚动哈希函数，该函数可以在 O(1) 时间内轻松地从一个子字符串更新到下一个子字符串。它还进行了额外的检查，因此如果当前哈希码与子字符串的哈希码匹配，算法实际上会检查每个字符以确保它们匹配。该算法在最坏的情况下需要时间 O(mn)，但在平均情况下要快得多（时间 O(m + n)）。

希望这可以帮助！

于 2013-05-07T17:19:12.567 回答
0

你的算法仍然是 O(nm)。

设 m 为模式的长度，n 为搜索字符串的长度。

在搜索字符串中的每个 (n - m) 位置，您正在创建一个子字符串并计算其哈希码。其中每一个都需要迭代 m 个字符。

复杂性不仅取决于您编写的代码，还取决于您调用的代码。

于 2013-05-07T17:16:07.413 回答