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

Question

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

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

在这个例子中,我们遍历整个字符串4次,这非常消耗.你会如何优化这个过程？

Answer 1

这使用a 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代码计算字符串中至少有一个外观substrings有多少,而我的解决方案计算任何一个外观有多少:substrings

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

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

我的结论是 - 去@Arup的解决方案.它不会比你的快,它只是更简洁,但我想不出更好的:)