Поиск. КМП-алгоритм

Недавно на досуге решил написать алгоритм КМП  (Кнута — Морриса — Пратта) для Scala.

Изначально, мне нужно было решить простенькую задачку — найти последовательность байт в потоке байтов. Сделал на Java. Потом, решил сделать тоже самое на Scala. Занятно, но в стандартной библиотеке коллекций Scala используется именно КМП поиск.

Вот мой вариант.

object KPM {
 
  def search(source: Seq[Any], m:Seq[Any]): Int = {
    // вычисляем значение префикс-функции
    val p = prefix(m)
    // длина строки которую ищем (вообще не обязательно строки)
    val length = m.size
    // кол-во совпадений
    var k = 0
    // позиция от начала
    var i = 0
    val it = source.iterator
    // перебираем все элементы
    while (it.hasNext && k < length) {
      // тек. элемент
      val current = it.next
      // pos - позиция тек. элемента в списке
      while (k > 0 && current != m(k)) {
        k = p(k - 1)
      }
 
      if (current == m(k)) {
        // еще одно совпадение
        k +=1
      }
      // следующая буква
      i+=1
    }
    // всё совпало
    if (k == length) {
      i - length
    } else {
      -1
    }
  }
 
  // префикс-функция
  def prefix(s: Seq[Any]):Array[Int]  = {
    val p = new Array[Int](s.size);
    p(0)=0
    for (i < - 1 to s.size-1) {
      // длина предыдущего префикса
      var length = p(i - 1)
      while (length > 0 && s(i) != s(length)) {
        length = p(length - 1)
      }
      if (s(length) == s(i)) length += 1
      p(i)=length;
    }
    return p;
  }
 
  def main(arr : Array[String]) = {
    val s = "abacaba"
    val m = "aca"
    val list = s.toList
    println(search(s, m))
    println(s.indexOf(m))
  }
}

Первое (и возможно самое сложно) что нужно сделать — понять что такое префикс-функция.

Но сначала нужно разобрать что значит вообще префикс и суффикс?
Если грубо префикс — это подстрока, которая начинается с первого символа. Для строки «happy«, строки ha, happ, h будут являться префиксами.

Суффикс — он как префикс, только с конца. Например, для строки «happy«, строки «appy«, «y»  будут суффиксами.

Префикс и суффиксы, которые совпадают со всей строкой целиком нас не интересуют.

Теперь введем понятие префикс-функции. Префикс-функции от строки — длина наибольшего префикса, который не совпадает с этой строкой и одновременно является её суффиксом. Если более простым языком, длина самого большого префикса, который также является и суффиксом (естественно, не совпадает со всей строкой).  А если еще проще, длина самых больших одинаковых кусков спереди и сзади строки.

Например.

pi("abacaba") = 3 
pi("aba") = 1 
pi("ab") =  0

На самом деле, используют префикс-функцию от двух аргументов — строки и числа. Строка — это исследуемая строка, а число — указывает длину подстроки для которой нужно считать префикс функцию.

Например для abacaba, Pi(«abacaba»,i)
P(«abacaba», 1) = «a»:0
P(«abacaba», 2) = «ab»:0
P(«abacaba», 3) = «aba»:1
P(«abacaba», 4) = «abac»:0
P(«abacaba», 5) = «abaca»:1
P(«abacaba», 6) = «abacab»:2
P(«abacaba», 7) = «abacaba»:3

получаем P(«abacaba») =0010123

Ну а потом читаем википедию 🙂