Изменения

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

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

18 байт добавлено, 22:07, 30 апреля 2014
Существование и единственность
1) <tex>|u| = |t| \rightarrow u = t \rightarrow u > s + t</tex>
2) <tex>|u| < |t| -> \rightarrow u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> {{---}} простая, <tex>t < u \rightarrow s + t < t < u</tex>
3) <tex>|u| > |t| \rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, <tex>s < s''</tex> и <tex>|s''| < |s| -> \rightarrow s + t < s'' + t</tex>
}}
Анонимный участник

Навигация