251
правка
Изменения
→Асимптотика
Рассмотрим три типа шагов в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на шаге <tex>k</tex> короткий, если <tex>2shift_k < suf_k + 1</tex>. Тогда эти три типа будут:
# Шаг с последующим шагом с прыжком.и
# Шаг с длинным сдвигом, без последующего шага с прыжком.
# Шаг с коротким сдвигом, без последующего шага с прыжком.
# <tex>cost_k = 1</tex> очевидным образом меньше, чем <tex>2shift_k</tex>, так как <tex>shift_k > 0</tex>.
# <tex>cost_k = suf_k + 1 \leqslant 2 shift_k</tex>, по определению длинных сдвигов.
# Так как в этой ситуации мы имеем <tex>shift_k < suf_k</tex>, единственный возможный вариант {{---}} , это когда обычный сдвиг применяется на шаге <tex>k</tex>. Тогда мы должны это запомнить. На следующем шаге, <tex>k + 1</tex>, мы что-то запомнили, что приводит к возможному турбо-сдвигу. Ситуация на шаге <tex>k + 1</tex>, {{---}} основная ситуация, когда турбо-сдвиг возможен. Прежде чем продолжить доказательство, мы сначала рассмотрим два случая и установим неравенства (по стоимости шага <tex>k</tex>), которые используем позже.
#* Случай (а): <tex>suf_k + shift_k \leqslant |p|</tex>. По определению турбо-сдвига, мы имеем <tex>suf_k - suf_{k+1} < shift_{k + 1}</tex>. Таким образом, <tex>cost_k = sufk + 1 \leqslant suf_{k+1} + shift_{k+1} + 1 \leqslant shift_k + shift_{k + 1}</tex>.
#* Случай (б): <tex>suf_k + shift_k > |p|</tex>. По определению турбо-сдвига, мы имеем <tex>suf_{k+1} + shift_k + shift_{k + 1} \geqslant m</tex>. Тогда <tex>cost_k \leqslant m \leqslant 2shift_k - 1 + shift_{k + 1}</tex>.
