Изменения

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

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

Нет изменений в размере, 23:19, 23 апреля 2015
м
Существование и единственность: исправлен мелкий баг
* <tex>|u| = |t| \Rightarrow u = t \Rightarrow u > s + t</tex> по пункту 1
* <tex>|u| < |t| \Rightarrow u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> {{---}} простая, и <tex>t < u </tex> по определению <tex> \Rightarrow s + t < t < u</tex>
* <tex>|u| > |t| \Rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, то её суффикс <tex> s'' </tex> меньше больше самой строки <tex> s </tex> в каком-то символе, значит, <tex> s + t < s'' + t</tex>
}}

Навигация