10.3. Вспомогательные утверждения

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

      Примеры: l(aba)=a, l(abab)=ab, l(ababa)=aba, l(abc) = пустое слово.

      10.3.1. Доказать, что все слова l(X), l(l(X)), l(l(l(X))) и т.д. являются началами слова X.

      Решение. Каждое из них (согласно определению) является началом предыдущего.

      По той же причине все они являются концами слова X.

      10.3.2. Доказать, что последовательность предыдущей задачи обрывается (на пустом слове).

      Решение. Каждое слово короче предыдущего.

      10.3.3. Доказать, что любое слово, одновременно являющееся началом и концом слова X (кроме самого X) входит в последовательность l(X), l(l(X)),...

      Решение. Пусть слово Y есть одновременно начало и конец X. Слово l(X) - самое длинное из таких слов, так что Y не длиннее l(X). Оба эти слова являются началами X, поэтому более короткое из них является началом более длинного: Y есть начало l(X). Аналогично, Y есть конец l(X). Рассуждая по индукции, можно предполагать, что утверждение задачи верно для всех слов короче X, в частности, для слова l(X). Так что слово Y, являющееся концом и началом l(X), либо равно l(X), либо входит в последовательность l(l(X)), l(l(l(X))), ..., что и требовалось доказать.

Другие записи

10.06.2016. 10.4. Алгоритм Кнута - Морриса - Пратта
Алгоритм Кнута - Морриса - Пратта (КМП) получает на вход слово X = x[1]x[2]...x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]..l[n], где…
10.06.2016. 10.5. Алгоритм Бойера - Мура
  Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея…
10.06.2016. 10.6. Алгоритм Рабина
Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образем длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли…
10.06.2016. 10.7. Более сложные образцы и автоматы
  Мы можем искать не конкретно слово, а подслова заданного вида. Например, можно искать слова вида a?b, где вместо ? может стоять любая буква (иными словами, нас интересует буква b на расстоянии…