В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:
index = -1
for i in xrange(len(haystack)-len(needle)+1):
success = True
for j in xrange(len(needle)):
if needle[j]<>haystack[i+j]:
success = False
break
if success:
index = i
break
print index
Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).
Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае.
