Изменения

Перейти к: навигация, поиск

Декомпозиция Линдона

5 байт убрано, 13:08, 6 мая 2014
Корректность
Во втором случае объединяем все найденные <tex>w</tex> с <tex>w'</tex> и получем новую строку <tex>w''</tex>.
Покажем, что <tex>w''</tex> является простой. Рассмотрим ее суффикс. Если он начинается в середине <tex>w</tex>, сравним его посимвольно со строкой <tex>s_2</tex>, и тогда в каком-то символе он окажется больше <tex>s_2</tex>, так как суффикс <tex> w'' </tex> начинается с <tex> u </tex> {{---}} суффикса <tex>w</tex>, а строка <tex>w</tex> {{---}} простая и по определению меньше всех своих суффиксов. Если суффикс начинается в <tex>w'</tex>, то при сравнении расхождение будет в символах <tex>s[j]</tex> и <tex>s[k]</tex>. Но <tex>s[j] < s[k]</tex>, так что суффикс больше <tex>w''</tex>. Если же суффикс начинается с первой позиции какой-то подстроки <tex>w</tex>, то отбросим общий префикс вида <tex>w + w + ... + ww \dots w</tex> и придем к предыдущему случаю.
В третьем случае просто выведем все <tex>w</tex> и продолжим обработку со строки <tex>w'</tex>, так как при добавлении <tex>s[k] </tex>, <tex>s_2</tex> перестанет удовлетворять требованиям, ведь в этом случае суффикс строки <tex> s_2 </tex> равный <tex> w'</tex> будет меньше <tex>w</tex>.

Навигация