Предположим, у нас есть строка S [0, ..., N]. Напомним, что i-я запись в массиве префиксов хранит длину максимального префикса S [0, ..., i], который соответствует суффиксу.
Мы можем вычислить префиксный массив P для шаблона $ subject (при условии, что $ не встречается в субъекте). Осталось найти такие индексы, что P [i] == length (pattern), что можно сделать за линейное время.