10.2. Повторения в образце - источник проблем

  •  
      10.2.1. Можно ли в предыдущих рассуждениях заменить слово "abcd" на произвольное слово?

      Решение. Нет, и проблемы связаны с тем, что в образце могут быть повторяющиеся буквы. Пусть, например, мы ищем вхождения слова "ababc". Вот появилась буква "a", за ней идет "b", за ней идет "a", затем снова "b". В этот момент мы с нетерпением ждем буквы "c". Однако - к нашему разочарованию - вместо нее появляется другая буква, и наш образец "ababc" не обнаружен. Однако нас может ожидать утешительный приз: если вместо "c" появилась буква "a", то не все потеряно: за ней могут последовать буквы "b" и "c", и образец-таки будет найден.

      Вот картинка, поясняющая сказанное:
      x y z a b a b a b c .... <- входное слово

      a b a b c <- мы ждали образца здесь

      a b a b c <- а он оказался здесь

      Таким образом, к моменту
      |
      x y z a b a b | <- входное слово
      |
      a b a b | c <- мы ждали образца здесь
      |
      a b | a b c <- а он оказался здесь
      |

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

      10.2.2. Указать состояния соответствующего автомата и таблицу перехода (новое состояние в зависимости от старого и читаемой буквы).

      Решение. По-прежнему состояния будут соответствовать наибольшему началу образца, являющемуся концом прочитанной части слова. Их будет шесть: 0, 1 ("a"), 2 ("ab"), 3 ("aba"), 4 ("abab"), 5 ("ababc"). Таблица перехода:
      Текущее Очередная Новое
      состояние буква состояние
      0 a 1 (a)
      0 кроме a 0
      1 (a) b 2 (ab)
      1 (a) a 1 (a)
      1 (a) кроме a,b 0
      2 (ab) a 3 (aba)
      2 (ab) кроме a 0
      3 (aba) b 4 (abab)
      3 (aba) a 1 (a)
      3 (aba) кроме a,b 0
      4 (abab) c 5 (ababc)
      4 (abab) a 3 (aba)
      4 (abab) кроме a,c 0

      Для проверки посмотрим, к примеру, на вторую снизу строку. Если прочитанная часть кончалась на "abab", а затем появилась буква "a", то теперь прочитанная часть кончается на "ababa". Наибольшее начало образца ("ababc"), являющееся её концом - это "aba".

      Философский вопрос: мы говорили, что трудность состоит в том, что есть несколько возможных положений образца, каждое из которых может оказаться истинным. Им соответствуют несколько начал образца, являющихся концами входного слова. Но конечный автомат помнит лишь самое длинное из них. Как же остальные?

      Философский ответ. Дело в том, что самое длинное из них определяет все остальные - это его концы, одновременно являющиеся его началами.

      Не составляет труда для любого конкретного образца написать программу, осуществляющую поиск этого образца описанным способом. Однако хотелось бы написать программу, которая ищет произвольный образец в произвольном слове. Это можно делать в два этапа: сначала по образцу строится таблица переходов конечного автомата, а затем читается входное слово и состояние преобразуется в соответствии с этой таблицей. Подобный метод часто используется для более сложных задач поиска (см. далее), но для поиска подслова существует более простой и эффективный алгоритм, называемый алгоритмом Кнута - Морриса - Пратта. (Ранее сходные идеи были предложены Ю.В.Матиясевичем.) Но прежде нам понадобятся некоторые вспомогательные утверждения.

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

10.06.2016. 10.3. Вспомогательные утверждения
  Для произвольного слова X рассмотрим все его начала, одновременно являющиеся его концами, и выберем из них самое длинное. (Не считая, конечно, самого слова X.) Будем обозначать его 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 на расстоянии…