scala - 尾递归 Knuth-Morris-Pratt 算法

Question

我创建了一个简单的 Knuth–Morris–Pratt algorithm 实现在斯卡拉。现在我想要花哨并以尾递归的方式做同样的事情。我的直觉告诉我这应该不会太难(表格和搜索部分)，但同样的感觉也告诉我这一定是有人已经完成的，可能比我更聪明。因此这个问题。你知道 Knuth-Morris-Pratt 算法的尾递归实现吗？

object KnuthMorrisPrattAlgorithm {
  def search(s: String, w: String): Int = {
    if (w.isEmpty) {
      return 0
    }

    var m = 0
    var i = 0
    val t = table(w)

    while(m + i < s.length) {
      if (w(i) == s(m + i)) {
        if (i == w.length - 1) {
          return m
        }
        i += 1
      } else {
        if (t(i) > -1) {
          i = t(i)
          m += i - t(i)
        } else {
          i = 0
          m += 1
        }
      }
    }

    return -1
  }

  def table(w: String): Seq[Int] = {
    var pos = 2
    var cnd = 0
    val t = Array(-1, 0) ++ Array.fill(w.size - 2)(0)

    while (pos < w.length) {
      if (w(pos - 1) == w(cnd)) {
        cnd += 1
        t(pos) = cnd
        pos += 1
      } else if (cnd > 0) {
        cnd = t(cnd)
      } else {
        t(pos) = 0
        pos += 1
      }
    }

    t
  }
}

Answer 1

我不知道那个算法是做什么的，但这是你的函数，尾递归:

object KnuthMorrisPrattAlgorithm {
  def search(s: String, w: String): Int = {
    if (w.isEmpty) {
      return 0
    }

    val t = table(w)

    def f(m: Int, i: Int): Int = {
      if (m + i < s.length) {
        if (w(i) == s(m + i)) {
          if (i == w.length - 1) {
            m
          } else {
            f(m, i + 1)
          }
        } else {
          if (t(i) > -1) {
            f(m + i - t(i), t(i))
          } else {
            f(m + 1, 0)
          }
        }
      } else {
        -1
      }
    }

    f(0, 0)
  }

  def table(w: String): Seq[Int] = {
    val t = Array(-1, 0) ++ Array.fill(w.size - 2)(0)

    def f(pos: Int, cnd: Int): Array[Int] = {
      if (pos < w.length) {
        if (w(pos - 1) == w(cnd)) {
          t(pos) = cnd + 1
          f(pos + 1, cnd + 1)
        } else if (cnd > 0) {
          f(pos, t(cnd))
        } else {
          t(pos) = 0
          f(pos + 1, cnd)
        }
      } else {
        t
      }
    }

    f(2, 0)
  }
}