Процессы и алгоритмы

Каждому прекрасному слову сопоставим позицию первой буквы последнего вхождения подслова в Докажем, что построено отображение является инъекцией, откуда будет следовать, что мощность всех прекрасных слов не превосходит мощности позиций всех букв в слова последнее же равно

Итак, предположим противное, тогда существуют два различных прекрасных слова и у которых совпадают позиции первых букв последних вхождений подслов и Пусть — количество букв в подслове Без ограничений общности будем считать, что Далее рассмотрим два случая.

Если то слово имеет своим префиксом слово но тогда первая буква второго вхождения слова в последнее вхождения слова является первой буквой какого-то вхождения слова что невозможно, ведь по предположению первая буква слова является первой буквой последнего вхождения слова

Пусть и — префикс последнего вхождения слова Во-первых, периодична с периодом Во-вторых, является префиксом слова но тогда она так же периодична с периодом Докажем, что тогда она периодична с периодом

Действительно, по теореме о линейном представлении НОД существуют такие целые числа и одинаковых знаков, что Будем считать, что второй случай разбирается аналогично.

Рассмотрим следующий процесс. Встанем на произвольную позицию в В силу периодичности, для любого на позиции при и при стоят те же буквы, что и на позиции Докажем, что мы сможем сделать операций первого вида и операций второго вида, тем самым придя в позицию

Пусть на некотором шаге мы сделали операций первого и операций второго вида. Если и то сделаем любую из операций, что возможно, поскольку текущая позиция удовлетворяет по крайней мере одному из требуемых неравенств. Если и то текущая позиция равна

но тогда мы можем сделать операцию первого типа, поскольку прибавление к текущей позиции даст не больше, чем то есть такая операция была возможно. Случай и рассматривается аналогично. Таким образом, в силу возрастания общего количество операций мы придем к случаю и чем получим требуемое. Таким образом, мы показали, что периодична с периодом Отсюда сразу следует, что и периодична с данным периодом.

Наконец, осталось заметить, что то есть то есть сдвинув все позиции последнего вхождения на мы получим снова слово поскольку индекс последней буквы равен что, как мы выяснили, меньше, чем а значит, каждая буква перешла в такую же. Тем самым, мы нашли вхождение позиция первой буквы больше изначальной.