使用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 的高阶函数而不是递归和 match/case 子句。

Answer 1

您或许可以使用这个 java 函数：

StringUtils.countMatches(stringToFindMatchesIn, keyWordToFind );

这将return关键字在字符串中出现的次数

Answer 2

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

此解决方案在发挥作用的同时还为您提供了可接受的性能。

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

Answer 3

如果其他人正在寻找非常有效且 semi-idomatic 的解决方案，请使用

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 快）one-liner 这可能适合您：

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

注：

第二个参数是正则表达式，这可能会导致意外结果，如果使用真正的正则表达式，速度会变慢。
它不计算重叠的子字符串，因此在最后一次测试中失败。
-1 作为 split 的第二个参数很重要。否则，末尾的子字符串将是 ignored.

使用scala查找给定字符串是另一个字符串的子字符串的次数

Finding how many times a given string is a substring of another string using scala

string

scala

find-occurrences