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

我在Scala中创建了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
  }
}

最佳答案

我不知道该算法的作用，但是这是您的函数，尾递归化：

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)
  }
}