Лексикографический порядок. Слова Линдона-Ширшова. Теорема Линдона о каноническом разбиении слова. Периодичность плюс порядок. Локальные периоды. Теорема о критическом разбиении. Задача поиска по образцу с использованием константной памяти. Критическое разбиение и алгоритм Крошмора. Алгоритм Бреслауэра для реального времени.