Блог программиста

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

Недавно на досуге решил написать алгоритм КМП  (Кнута — Морриса — Пратта) для 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

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

vit

,
,