Изменения
→Основные определения
{{Определение
|id=def1.
|definition='''Простая строка''' {{---}} строка, которая лексикографически меньше любого своего собственного суффикса.
}}
2. <tex>s + t</tex> {{---}} простая
|proof=
1. Так как <tex>s < t</tex>, то либо <tex>s</tex> является префиксом <tex>t</tex>, тогда: <tex>s + t = s + s + x</tex> <tex>s + s + x < s + x</tex> <tex>s + x < x</tex> Следовательно <tex>t <</tex> любого суффикса <tex>t</tex> (так как по условию <tex>t</tex> явлеяется простой строкой), либо <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow </tex>. Из обоих ситуаций следует, что <tex> s + t < t</tex>
2. Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>. Тогда рассмотрим 3 возможных случая:
|statement= Строка <tex>T</tex> длины <tex>n</tex> может храниться в структуре данных памяти <tex>\mathcal{O}(n)</tex>, которая позволяет вычислять максимальный суффикс любой подстроки <tex>T</tex> за <tex>\mathcal{O}(1)</tex> времени. Данную структуру данных можно построить за <tex>\mathcal{O}(n)</tex> времени.
}}
==См. также==
* [[Алгоритм Крочемора]]
* [[Суффиксный массив]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
==Примечания==
