Сравнение строк - алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта

При построении конечного автомата для поиска подстроки в тексте легко построить переходы из начального состояния в конечное принимающее состояние: эти переходы помечены символами подстроки (см. рис. 1). Проблема возникает при попытке добавить другие символы, которые не переводят в конечное состояние.
Начало построения автомата для поиска подстроки hello

Начало построения автомата для поиска подстроки hello

Алгоритм Кнута-Морриса-Пратта основан на принципе конечного автомата, однако он использует более простой метод обработки неподходящих символов. В этом алгоритме состояния помечаются символами, совпадение с которыми должно в данный момент произойти. Из каждого состояния имеется два перехода: один соответствует успешному сравнению, другой - несовпадению. Успешное сравнение переводит нас в следующий узел автомата, а в случае несовпадения мы попадем в предыдущий узел, отвечающий образцу. Пример автомата Кнута-Морриса-Пратта для подстроки ababcb приведен на рисунке 2.
Полный автомат Кнута-Морриса-Пратта для подстроки ababcb

Полный автомат Кнута-Морриса-Пратта для подстроки ababcb

При всяком переходе по успешному сравнению в конечном автомате Кнутта-Морриса-Пратта происходит выборка нового символа из текста. Переходы, отвечающие неудачному сравнению, не приводят к выборке нового символа; вместо этого они повторно используют последний выбранный символ. Если мы перешли в конечное состояния, то это означает, что искомая подстрока найдена. Проверьте текст abababcbab на автомате, изображенном на рисунке 3, и посмотрите, как происходит успешный поиск подстроки.
Вот полный алгоритм поиска:

subLoc = 1	// указатель текущего сравниваемого символа в подстроке
textLoc = 1	// указатель текущего сравниваемого символа в тексте

while textLoc <= length(text) and subLoc <= length(substring) do
	if subLoc = 0 or text[textLoc] = substring[subLoc] then
		textLoc = textLoc + 1
		subLoc = subLoc + 1
	else	// совпадения нет; переход по несовпадению
		subLoc = fail[subLoc]
	end if
end while

if (subLoc > length(substring)) then
	return textLoc - length(substring) + 1	//найденное совпадение
else
	return 0	// искомая подстрока не найдена
end if

Прежде, чем перейти к анализу этого процесса, рассмотрим как задаются переходы по несовпадению. Заметим, что при совпадении ничего особенного делать не надо: происходит переход к следующему узлу. Напротив, переходы по несовпадению определяются тем, как искомая подстрока соотносится сама с собой. Например, при поиске подстроки ababcb нет необходимости возвращаться назад на четыре позиции при необнаружении символа c. Если уж мы добрались до пятого символа в образце, то мы знаем, что первые четыре символа совпали, и поэтому символы ab в тексте, отвечающие третьему и четвертому символам образца, совпадают также с первым и вторым символами образца. Вот как выглядит алгоритм, задающий эти соотношения в подстроке:

fail[1] = 0
for i = 2 to length(substring) do
	temp = fail[i - 1]
	while (temp > 0) and (substring[temp] /= substring[i - 1]) do
		temp = fail[temp]
	end while
	fail[i]	 = temp + 1
end for

Сайт управляется системой uCoz