VPF::Поиск подстроки в строке по КМП

Pakshin A. S.

Дата 5.11.2006, 22:56 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: 21
Всего: 61

Вот изучал КМП. Везде были примеры с таблицами дял управления переходами, но я тут сделал без таблицы:

Код


// КМП поиск
function Search2(const str, substr: string): TResult;
(*
  str - исходная строка
  substr - подстрока, которую нужно найти
  Result - результат измерений
*)
var
  i, j: integer; // i - позиция в строке
                 // j - позиция в подстроке
  str_len, sub_len: integer; // длины строки и подстроки соответсвенно
  kf: integer; // Количество одинаковых символов в строке, начиная с ее начала.
               // Нfпример, в строке '223' kf = 2
  kf_save: integer; // ну сэйв kf
begin
  str_len:=Length(str);
  sub_len:=Length(substr);
  with Result do
    begin
      // Инициализация результатов измерений
      Shifts:= 0;
      Comparisons:= 0;
      // Считаем, сколько одинаковых символов в подстроке с ее начала
      kf:=1;
      while (kf < sub_len) and (substr[kf] = substr[kf+1]) do
        inc(kf);
      kf_save:=kf; // СОхраняем значение kf, так как само kf будет изменяться
      j:= 1; // Приготавливаемся к началу подстроки
      i:= 1; // Приготавливаемся к началу строки
      while (i <= str_len) and (j <= sub_len) do
        (*
          Выполняем цикл до тех пор, пока мы не вышли за пределы наших строк.

          Если мы вышли за перделы подстроки, значит она найдена в строке: можно радоватсья!
        *)
        begin
          inc(Comparisons);
          if (j = 0) or (str[i] = substr[j]) then
            (*
              j = 0 является флагом, что мы должны начать рассматривать подстроку с ее начала, но при этом
              передвинутсья по исходной строке

              втора часть условия отвечае за то, что мы просто будем шагать и по строке и по подстроке
              вместе, т. е. будет наблюдаться совпадение символов
            *)
            begin
              inc(i);
              inc(j);
              if kf < kf_save then
                inc(kf);
              if j = 1 then
                dec(Comparisons)
            end
          else
            begin
              inc(Shifts);
              if j = kf+1 then
                (*
                  Этим условием мы проверяем: находимся ли мы на символе, до которого у нас все символы совпали
                  и они одинаковы. Т. о. мы может переходить не на начало подстроки, а на предыдущий символ, что
                  отражается таблицей в табличном КМП:
                  0 1 2 соответсвует сроке 112
                  Рассмотрим ситуацию:
                    строка: 1112
                    подстрока 112

                    kf=2

                    первый этап алгоритма... строки стоят так:
                      1112           i=1
                      112            j=1
                    не совпадает по третьему символу, значит мы могли без учета совпадений символов сдвинутсья на
                    позицию:
                             1112    i=3
                               112   j=1
                    что не соответсвует нужному, поэтмоу мы смещаемся на следующем шаге тким образом:
                      1112           i=3
                       112           j=2
                *)
                begin
                  j:=kf;
                  dec(kf); // Понизим количество совпавших символов, что отражается в таблице в обычном КМП.
                end
              else
                begin
                  kf:=kf_save; // Восстанавливаем значение kf
                  if j > 1 then
                    (*
                      Здесь мы оставляем текущую позицию в исходной строке, а подстроку начинаем рассматривать с первого
                      символа, что в точности повторяет алгоритм КМП
                    *)
                    j:=1
                  else
                    (*
                      Если у нас i-ый символ строки ен совпал с первым символом подстроки, то мы должны переместиться на один
                      символ по ходу строки, а подстроку будем рассматривать само-собой с ее начала.
                    *)
                    j:= 0
                end;
            end
        end;
      Found:=j > sub_len // Возвращаем результат поиска
    end
end; // end of Search2()

Похоже на истину или нет?

Это сообщение отредактировал(а) Pakshin A. S. - 6.11.2006, 01:17

Guedda

Дата 6.11.2006, 08:56 (ссылка)

(нет голосов)

Загрузка ...

Подрывник

Профиль
Группа: Завсегдатай
Сообщений: 3137
Регистрация: 27.12.2005
Где: Ростов-на-Дону

Репутация: 14
Всего: 78

Извиняюсь за столь дикий вопрос:
А что такое КМП? Интересно очень знать...

--------------------

Ll 2

Pakshin A. S.

Дата 6.11.2006, 22:27 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: 21
Всего: 61

Алгоритм поиска подстроки в строке Кнута-Мориса-Пратта

ОТвет на поставленный мною вопрос: не верный алгоритм, может давать сбои... Придется все-таки через массив работать...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Delphi: Общие вопросы \| Следующая тема »