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