Изменения

что совпадает с текстом. Она Этому предшествует буквасимвол, которая который не

Рассмотрим три типа стадий в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на стадии <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>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>.}}