KMP算法scala实现

KMP算法是一种字符串匹配算法，可以在一个主串中查找一个模式串的出现位置。以下是KMP算法的Scala实现：

def kmp(s: String, p: String): Int = {
  val next = getNext(p)
  var i = 0
  var j = 0
  while (i < s.length && j < p.length) {
    if (j == -1 || s.charAt(i) == p.charAt(j)) {
      i += 1
      j += 1
    } else {
      j = next(j)
    }
  }
  if (j == p.length) i - j else -1
}

def getNext(p: String): Array[Int] = {
  val next = Array.ofDim[Int](p.length)
  next(0) = -1
  var i = 0
  var j = -1
  while (i < p.length - 1) {
    if (j == -1 || p.charAt(i) == p.charAt(j)) {
      i += 1
      j += 1
      next(i) = j
    } else {
      j = next(j)
    }
  }
  next
}

在这个实现中，`kmp`方法接收两个字符串`p`和`s`，其中`s`是主串，`p`是模式串。`getNext`方法用于计算模式串的next数组。在`kmp`方法中，使用双指针`i`和`j`分别指向`s`和`p`的当前比较位置，如果当前字符匹配，则两个指针都向后移动；否则，移动模式串的指针`j`到next数组对应位置上的值，继续和主串中的字符比较。如果`j`等于模式串的长度，说明匹配成功，返回当前主串中匹配的起始位置；否则，匹配失败，返回-1。