Изменения

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

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

81 байт добавлено, 13:12, 13 февраля 2018
Существование и единственность
2. <tex>s + t</tex> {{---}} простая
|proof=
1. Так как <tex>s < t</tex>, то либо <tex>s</tex> является префиксом <tex>t</tex>, либо <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow s + t < t</tex>
2. Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>. Тогда рассмотрим 3 возможных случая:
Анонимный участник

Навигация