Префикс функция. Алгоритм Кнута-Морриса-Пратта

Префикс функция

Значением префикс функции от строки s[0, ..., n-1] является массив натуральных чисел π‎[0, ..., n-1], где π‎[i] определяется как максимальная длина собственного префикса, совпадающего с суффиксом. Значение π‎[0] естественно равно 0, т.к. у строки длинны 1 нет собственного префикса (собственный префикс - префикс не совпадающий со всей строкой).

Рассмотрим следующий случай:

Для элемента 0 значение π равно 0.

π[1] = 0, т.к. s[0] != s[1]

π[2] = 1, т.к. максимальный собственный префикс длины 1 (s[0]) совпадает с суффиксом (s[2])

π[3] = 2, т.к. максимальный собственный префикс длины 2 (s[0...1]) совпадает с суффиксом (s[2...3])

Можем заметить следующую закономерность, что, если значение на предыдущем шаге s[i] не 0, то можно сравнить следующий элемент s[i+1] со следующим элементом префикса p[j+1] и если значения равны, то следующее значение массива префикс функции будет равно π[i+1] = π[i] + 1. В противном случае отнимаем от префикса по одному элементу, пока s[i+1] не будет равен s[p], либо p не станет равен 0.
Такой алгоритм будет работать за O(n)

Псевдокод:

π[0] = 0
i = 1
j = 0
while s[i] != s[length-1]:
    if s[i] == s[j]:
         π[i] = j + 1
        i += 1
        j += 1
    else if j == 0:
        π[i] = 0
        i += 1
    else:
        j = π[j-1]

На C++ функция будет выглядеть примерно следующим образом:

vector<size_t> prefix_func(string_view str)
{
	size_t length = str.size();
	vector<size_t> p(length);
	
    p[0] = 0;
	for (size_t i = 1, j = 0; i < length;)
	{
	    if (str[i] == str[j])
		{
			p[i] = j + 1;
			i++;
			j++;
		}
		else if (j == 0)
		{
			p[i] = 0;
			i++;
		}
		else
			j = p[j - 1];
	}
	
    return p;
}

Алгоритм КМП

Алгоритм КМП - это алгоритм для поиска всех вхождений прототипа в исходном тексте, те для поиска подстроки. Алгоритм основывается на префикс функции и работает за O(длина прототипа + длина текста).

Идея алгоритма заключается в том, что мы можем посчитать префикс функция для исходной строки относительно прототипа. Т.е. мы можем склеить прототип с исходной строкой и передать в префикс функцию. Таким образом при проходе по в цикле по части исходной строки алгоритм будет сравнивать символы (суффикс) исходной строки с символами (префиксом) прототипа. В итоге в массиве префикс функции получится часть значений, соответствующих длине прототипа (данные позиции будут являться концами вхождений прототипа).

Для того, чтобы у нас не получились значения в массиве больше длины прототипа, нужно добавить между строкой и прототипом разделитель, не входящий в алфавит. К примеру так p + "#" + s.

Рассмотрим поиск всех вхождений прототипа aab в baabcabaabaabab

Итак, на выходе префикс функции мы получим нижний массив, и для того, чтобы нам найти начальные позиции вхождения подпоследовательности нам всего лишь останется пройти в цикле по данному массиву, начиная с 4-го элемента (длина прототипа + разделитель), и сравнивать его значения с длиной прототипа, если значения равны, то значит данная позиция является концом вхождения (чтобы получить начало просто вычитаем из данной позиции длину прототипа).

Реализация на c++ может выглядеть следующим образом

vector<size_t> kamp_search(const string& text, const string& prototype)
{
	size_t prototype_length = prototype.size();
	vector<size_t> find_pos;
	vector<size_t> p(prefix_func(prototype + "#" + text));
	
    for (size_t i = 0; i < text.size(); ++i)
		if (p[find_length + 1 + i] == prototype_length)
			find_pos.emplace_back(i + 1 - prototype_length);
			
    return find_pos;
}

Наш телеграм: https://t.me/hw_algos