使用Scala查找一个给定字符串在另一个字符串中作为子字符串出现的次数

Question

如何使用Scala找到给定字符串在另一个字符串中作为子字符串出现次数的优雅方法？

以下测试用例应该清楚说明要求：

import org.scalatest.FunSuite

class WordOccurrencesSolverTest extends FunSuite {

  private val solver = new WordOccurrencesSolver()

  test("solve for a in a") {
    assert(solver.solve("a", "a") === 1)
  }

  test("solve for b in a") {
    assert(solver.solve("b", "a") === 0)
  }

  test("solve for a in aa") {
    assert(solver.solve("a", "aa") === 2)
  }

  test("solve for b in ab") {
    assert(solver.solve("b", "ab") === 1)
  }

  test("solve for ab in ab") {
    assert(solver.solve("ab", "ab") === 1)
  }

  test("solve for ab in abab") {
    assert(solver.solve("ab", "abab") === 2)
  }

  test("solve for aa in aaa") {
    assert(solver.solve("aa", "aaa") === 2)
  }
}

这是我对一个问题的解决方案，虽然不太自豪：

class WordOccurrencesSolver {

  def solve(word: String, text: String): Int = {
    val n = word.length
    def solve(acc: Int, word: String, sb: String): Int = sb match {
      case _ if sb.length < n => acc
      case _ if sb.substring(0, n) == word => solve(acc + 1, word, sb.tail)
      case _ => solve(acc, word, sb.tail)
    }
    solve(0, word, text)
  }

}

我认为一定有一个简洁的一行代码，可以利用Scala的高阶函数而不是递归和匹配/案例子句。

- GA1

---

嗯...我建议你远离寻找一行代码的诱惑。首先要专注于解决方案的时间复杂度。只有在处理好这个问题之后，才应该寻找一行代码或优雅的解决方案。尽量思考一个避免使用子字符串（实际上是O(n)）的解决方案，以免使你的解决方案在性能上非常差劲。 - sarveshseri

同样地，对于字符串来说，.tail 的时间复杂度也是 O(n)，因此应该避免使用。 - sarveshseri

好的，我不知怎么就错过了这个要点。 - GA1

Answer 1

如果你正在寻找一种惯用的Scala解决方案，那么可以使用sliding创建滑动窗口迭代器，并计算与目标字符串相等的窗口数量。

这种解决方案不仅具有功能性，而且性能也是可接受的。

def countOccurrences(src: String, tgt: String): Int =
  src.sliding(tgt.length).count(window => window == tgt)

- sarveshseri

---

看起来很不错。这个解决方案的时间复杂度是多少？ - GA1

嗯...假设你的src长度为m，而tgt长度为n。那么第一步-创建窗口迭代器是O(m)。该迭代器将有m-n个窗口字符串。第二步-计数涉及将长度为n的窗口字符串与tgt字符串进行比较，因此它是O(n*m)。所以总体复杂度是O(m*n)。 - sarveshseri

很好，这正是我想要找到的解决方案。但我仍然很好奇。根据您的记号，是否存在可以以 O(n) 实现相同功能的算法（不一定是一行代码）？也就是说，存在一些与 src 的长度无关的算法，以 O 表示。 - GA1

子字符串搜索是一个非常研究的领域，因此有许多优秀的算法，其中一些是条件依赖的，而另一些则是普遍适用的。您可以在这里详细了解它们 - http://www-igm.univ-mlv.fr/~lecroq/string/。但请注意，这篇文章是以数学为中心的观点来写的。不过，您可以在谷歌上搜索更简单的解释这些算法的方法。 - sarveshseri

但是不会有任何O(n)的算法，因为那是不可能的。即使是O(m)的算法也应该是不可能的。 - sarveshseri

Answer 2

您可以使用这个Java函数：

你可能会用到这个Java函数：

StringUtils.countMatches(stringToFindMatchesIn, keyWordToFind );

这将返回字符串中关键字出现的次数。

- iPhantomGuy

---

我认为 OP 不允许使用那个。这看起来像一个作业问题/练习。 - sarveshseri

StringUtils不是来自核心Java库，而是来自Apache Commons！而且它也不仅仅适用于Scala。 - Viacheslav Rodionov

@ViacheslavRodionov 在Scala上工作，看起来是正确的（做了需要的事情）。而且它可能比上面的答案更高效。 - Mikhail Ionkin

@MikhailIonkin请再次阅读原始问题以及我上面的评论。仅仅因为这段代码能够工作并不足以将其作为解决方案提出。 - Viacheslav Rodionov

@ViacheslavRodionov 在谷歌上我找到了这个问题，这个答案对我很有帮助。它既优雅又经过测试（生产质量），并且是一个“一行”解决方案。是的，这个问题的Scala解决方案已经清晰了，但我不确定它是否适用于所有情况。 - Mikhail Ionkin

Answer 3

如果有人正在寻找一种非常高效且半语言化的解决方案，请使用：

extension (s: String) def countSubstr(sub: String, overlap: Boolean = false): Int = {
  if (sub.isEmpty) throw IllegalArgumentException("substring must not be empty")
  val d = if (overlap) 1 else sub.length
  @tailrec
  def count(pos: Int, acc: Int): Int =
    s.indexOf(sub, pos) match {
      case -1 => acc
      case j => count(j + d, acc + 1)
    }
  count(0, 0)
}

如果您需要与Scala 2兼容或者不喜欢使用扩展，请使用：

def countSubstr(s: String, sub: String, overlap: Boolean = false): Int = {
  ...

当 overlap = false 时，运行时间为 O(s.length)。

没有对象分配，@tailrec 方法被优化为跳转，match 被优化为 if。

正如您最后的示例所示，您想允许重叠，因此速度略慢（但最坏情况下为 O(s.length*sub.length)）。

---

如果您正在寻找一个（速度较慢，但仍可能比sliding更快）的一行代码，那么这个可能适合您：

  def countSubstr(s: String, regex: String): Int =
    s.split(regex, -1).length - 1

注意：

• 第二个参数是一个正则表达式，如果使用真实的正则表达式可能会导致意外结果并且运行速度较慢。
• 它不计算重叠的子字符串，所以在最后一个测试中失败了。
• split 的第二个参数的 -1 很重要。否则，末尾的子字符串将被忽略。

- anselm