Изменения

|proof= Разобьём поиск на стадиишаги, каждая каждый из которых будет состоять из двух операций: сканирования и сдвига. На стадии шаге <tex>k</tex> мы назовём будем называть <tex>suf_k</tex> длину суффикса шаблона, что совпадает с текстом. Этому предшествует символ перед Перед суффиксом шаблонабудет символ, который не совпадает с соответствующим символом в тексте (в случае когда <tex>suf_k</tex> не соответствует длине шаблона). Мы также назовём будем называть <tex>shift_k</tex> длину сдвига, сделанного на этапе шаге <tex>k</tex>.

Рассмотрим три типа стадий шагов в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на стадии шаге <tex>k</tex> короткий, если <tex>2shift_k < suf_k + 1</tex>. Тогда эти три типа сдвигов будут: # Стадия Шаг с последующей стадией последующим шагом с прыжком.# Стадия Шаг с длинным сдвигом, без последующей стадии последующего шага с прыжком.# Стадия Шаг с коротким сдвигом, без последующей стадии последующего шага с прыжком.Идея доказательства состоит в амортизации сравнения со сдвигами. Определим стоимость шага <tex>cost_k</tex> следующим образом:* Если стадия шаг <tex>k</tex> имеет тип (1), <tex>cost_k = 1</tex>.* Если стадия шаг <tex>k</tex> имеет тип (2) или (3), стоимость <tex>cost_k = suf_k + 1</tex>.В случае стадии шага типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение той того же стадиишага, являютсястоимостью последующих этаповшагов. Общее количество сравнений выполняемых алгоритмом это сумма стоимостейшагов. Мы хотим доказать, что <tex> \sum cost < 2 \sum shifts</tex>. Во второй <tex> \sum </tex> длину последнего сдвига заменим <tex>m</tex>. Даже с этим предположением, мы имеем <tex> \sum shifts < |t|</tex>, и если неравенство выполняется, тo <tex> \sum cost < 2|t|</tex>.

Для стадии шага типа (1), <tex>cost_k = 1</tex> очевидным образом меньше, чем <tex>2shift_k</tex>, так как <tex>shift_k > 0</tex>. Для стадии шага типа (2), <tex>cost_k = suf_k + 1 \leqslant 2 shift_k</tex>, по определению длинных сдвигов. Остается рассмотреть стадии шаг типа (3). Так как в этой ситуации мы имеем <tex>shift_k < suf_k</tex>, единственный вариант, что обычный сдвиг применяется на стадии шаге <tex>k</tex>. Тогда мы запоминаем этот момент. На следующей стадииследующем шаге, <tex>k + 1</tex>, мы что-то запомнили, что приводит к возможному турбо-сдвигу. Ситуация на стадии шаге <tex>k + 1</tex>, основная ситуация, когда турбо-сдвиг возможен. Прежде чем продолжить доказательство, мы сначала рассмотрим два случая и установим неравенства (по стоимости стадии шага <tex>k</tex>), которые используем позже.

Можно считать, что на стадии шаге <tex>k + 1</tex> случай (б) имеет место, потому что это дает нам верхнюю границу <tex>cost_k</tex> (это верно, если <tex>shift_k \geqslant 2</tex>, случай <tex>shift_k = 1</tex> можно обрабатывать напрямую). Если стадия шаг <tex>k + 1</tex> типа (1), то <tex>cost_{k + 1} = 1</tex>, а затем <tex>cost_k + cost_{k+1} \leqslant 2shift_k + shift_{k+1}</tex>, что даже лучше, чем ожидалось. Если на стадии шаге <tex>k + 1</tex> мы имеем <tex>suf_{k + 1} \leqslant shift_{k + 1}</tex>, то мы получим то, что ожидалось: <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1}</tex>.Последняя ситуация для рассмотрения, когда на стадии шаге <tex>k + 1</tex> мы имеем <tex>suf_{k + 1} > shift_{k + 1}</tex>. Это означает, что, как уже упоминалось ранее, обычный сдвиг применяется на стадии шаге <tex>k + 1</tex>.

Таким образом, приведенный выше анализ также применяется на стадии шаге <tex>k + 1</tex>, и, так как только случай (а) может произойти тогда мы получаем <tex>cost_{k + 1} \leqslant shift_{k + 1} + shift_{k + 2}</tex>. Мы, наконец, получаем <tex>cost_k + cost_{k + 1} \leqslant 2shift_k + 2shift_{k + 1} + shift_{k + 2}</tex>.Последний аргумент, доказывающий первый шаг индукции: если все стадии шаги <tex>k</tex> до <tex>k + j</tex> таковы, что <tex>suf_k > shift_k,... , suf_{k + j} > shift_{k + j}</tex>, то <tex>cost_k + ... + cost_{k + j} \leqslant 2shift_k + ... + 2shift_{k + j} + shift_{k + j + 1}</tex>.