Макс нет раз конкретный символ в строке в алгоритме Кнута Морриса Пратта сравнивается со строкой?

Question

Позволять

T:String
P:pattern

Каково максимальное число случаев, когда конкретный символ в строке (T) в алгоритме Кнута Морриса Пратта сравнивается с шаблоном (P)?

Answer 1

|P|, Вот пример:

P = aaa...a(n times)T = aaa...a(n times)b

Когда мы достигаем bтекущее значение счетчика n, Каждое сравнение уменьшает его ровно на единицу. Таким образом, это делает именно n итерации, пока не достигнет нуля.

Почему это верхняя граница?

Очевидно, что количество сравнений не более |P|(каждое сравнение уменьшает значение префиксной функции как минимум на единицу и никогда не может превышать |P|).