10.1. Простейший пример

  •  
      10.1.1. Имеется последовательность символов x[1]..x[n]. Определить, имеются ли в ней идущие друг за другом символы "abcd". (Другими словами, требуется выяснить, есть ли в слове x[1]..x[n] подслово "abcd".)

      Решение. Имеется примерно n (если быть точным, n-3) позиций, на которых может находиться искомое подслово в исходном слове. Для каждой из позиций можно проверить, действительно ли там оно находится, сравнив четыре символа. Однако есть более эффективный способ. Читая слово x[1]..x[n] слева направо, мы ожидаем появления буквы 'a'. Как только она появилась, мы ищем за ней букву 'b', затем 'c', и, наконец, 'd'. Если наши ожидания оправдываются, то слово "abcd" обнаружено. Если же какая-то из нужных букв не появляется, мы оказываемся у разбитого корыта и начинаем все сначала.

      Этот простой алгоритм можно описать в разных терминах. Используя терминологию так называемых конечных автоматов, можно сказать, что при чтении слова x слева направо мы в каждый момент находимся в одном из следующих состояний: "начальное" (0), "сразу после a" (1), "сразу после ab" (2), "сразу после abc" (3) и "сразу после abcd" (4). Читая очередную букву, мы переходим в следующее состояние по правилу
      Текущее Очередная Новое
      состояние буква состояние
      0 a 1
      0 кроме a 0
      1 b 2
      1 a 1
      1 кроме a,b 0
      2 c 3
      2 a 1
      2 кроме a,c 0
      3 d 4
      3 a 1
      3 кроме a,d 0

      Как только мы попадем в состояние 4, работа заканчивается.

      Соответствующая программа очевидна (мы указываем новое состояние, даже если оно совпадает со старым; эти строки можно опустить):
      i:=1; state:=0;
      {i - первая непрочитанная буква, state - состояние}
      while (i <> n+1) and (state <> 4) do begin
      if state = 0 then begin
      if x[i] = a then begin
      state:= 1;
      end else begin
      state:= 0;
      end;
      end else if state = 1 then begin
      if x[i] = b then begin
      state:= 2;
      end else if x[i] = a then begin
      state:= 1;
      end else begin
      state:= 0;
      end;
      end else if state = 2 then begin
      if x[i] = c then begin
      state:= 3;
      end else if x[i] = a then begin
      state:= 1;
      end else begin
      state:= 0;
      end;
      end else if state = 3 then begin
      if x[i] = d then begin
      state:= 4;
      end else if x[i] = a then begin
      state:= 1;
      end else begin
      state:= 0;
      end;
      end;
      end;
      answer := (state = 4);

      Иными словами, мы в каждый момент храним информацию о том, какое максимальное начало нашего образца "abcd" является концом прочитанной части. (Его длина и есть то "состояние", о котором шла речь.)

      Терминология, нами используемая, такова. Слово - это любая последовательность символов из некоторого фиксированного конечного множества. Это множество называется алфавитом, его элементы - буквами. Если отбросить несколько букв с конца слова, останется другое слово, называемое началом первого. Любое слово также считается своим началом. Конец слова - то, что останется, если отбросить несколько первых букв. Любое слово считается своим концом. Подслово - то, что останется, если отбросить буквы и с начала, и с конца. (Другими словами, подслова - это концы начал, или, что то же, начала концов.)

      В терминах индуктивных функций (см. раздел 1.3) ситуацию можно описать так: рассмотрим функцию на словах, которая принимает два значения "истина" и "ложь" и истинна на словах, имеющих "abcd" своим подсловом. Эта функция не является индуктивной, но имеет индуктивное расширение

      x ->длина максимального начала слова abcd, являющегося концом x

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

10.06.2016. 10.2. Повторения в образце - источник проблем
  10.2.1. Можно ли в предыдущих рассуждениях заменить слово "abcd" на произвольное слово? Решение. Нет, и проблемы связаны с тем, что в образце могут быть повторяющиеся буквы. Пусть, например, мы ищем…
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 и будем двигать его по входному слову. Нас интересует, не совпадает ли…