Вот изучал КМП. Везде были примеры с таблицами дял управления переходами, но я тут сделал без таблицы:
| Код |
// КМП поиск
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()
|
Похоже на истину или нет? |