![]() |
|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
![]() |
|
Опции темы | Поиск в этой теме | Опции просмотра |
|
#1
|
|||
|
|||
![]() Здравствуйте! Подскажите пожалуйста, алгоритм расчета массива сдвигов в алгоритме Кнута-Морриса-Пратта (поиск первого вхождения слова в текст). Нашел несколько статей, но там как-то непонятно все, никак не могу разобраться
|
#2
|
||||
|
||||
![]() Код:
Function pos (t,p : String) : integer; var F : array[0..len] of integer; k,i : integer; {t - подстрока;p - соотвественно строка} {len - сумма длин строки и подстроки } begin F[1] := 0; k := 0; For i := 2 to length(T) do begin While (k > 0) and (T[k+1] <> T[i]) do k := F[k]; if T[k+1] = T[i] Then Inc(k); {функция Inc от числа сопоставима со строчкой число:=число+1} F[i] := k; end; k := 0; For i := 1 to length(P) do begin While (k > 0) and ( T[k+1] <> P[i]) do k := F[k]; if T[k+1] = T[i] Then Inc(k); if k = length(T) Then Begin pos := i+length(t); {Здесь обрабатываются полученные данные после того как мы нашли подстроку, можно сделать результатом работы функции не только положение подстроки} Break End; end; end; |