ruby - 计算 ruby​​ 中子字符串列表出现次数的最快方法

Question

我的问题很简单，我有一个子字符串列表，我必须计算特定字符串中包含多少个子字符串。 这是我的代码:

string = "..."
substrings = ["hello", "foo", "bar", "brol"]
count = 0
substrings.each do |sub|
    count += 1 if string.include?(sub)
end

在这个例子中，我们遍历了整个字符串 4 次，这非常耗时。 您将如何优化此流程？

Answer 1

这使用了 Regexp.union只遍历字符串一次:

string = 'hello there! this is foobar!'
substrings = ["hello", "foo", "bar", "brol"]

string.scan(Regexp.union(substrings)).count
# => 3

虽然这个解决方案在输入较小的情况下明显较慢，但它的复杂度较低 - 对于长度为 n 的字符串和长度为 m 的子字符串，原始解决方案的复杂度为 O(m*n)，而这个解决方案的复杂度为O(m+n)。

---

更新
再次阅读问题和我的回答后，我得出的结论是，这不仅是一个过早的优化(正如@Max 指出的那样)，而且我的回答在语义上与 OP 不同 .

让我解释一下 - OP 代码计算有多少子字符串在字符串中有至少一次出现，而我的解决方案计算有多少次出现 任何 子串:

op_solution('hello hello there', ["hello", "foo", "bar", "brol"])
# => 1
uri_solution('hello hello there', ["hello", "foo", "bar", "brol"])
# => 2

这也解释了为什么我的解决方案如此缓慢，即使对于长字符串也是如此 - 虽然它只对输入字符串进行一次传递，但它必须传递所有，而原始代码停止在单词的第一次出现。

我的结论是——采用@Arup 的解决方案。它不会比你的快，它只是更简洁，但我想不出更好的了:)