|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
Поиска слова по алгоритму Рабина - Карпа
Всем привет! Имеется программа поиска слова по алгоритму Рабина - Карпа
Код:
function Karp(s,x:string):longint; var hs1,hs2:longint; i:integer; begin crsn:=0; hs1:=Hash(x,1,length(x)); for i:=1 to length(s)-length(x) do begin inc(crsn); hs2:=Hash(s,i,length(x)); // <- Вот тут if (x=copy(s,i,length(x))) and (hs1=hs2) then begin Karp:=i; break; end; end; form1.Comp2.text:=inttostr(crsn); end; function Hash(st:string; nr,dl:integer):longint; var i,h:integer; begin h:=0; for i:=nr to nr+dl-1 do h:=(h*125+ord(st[i])) mod 1356; Hash:=h; end; Но мой преподаватель говорит, что мол хеш не меняется а должен все время пересчитываться. Отнимать старое и добавлять новое. Как то так он и сказал в месте где я пометила. Но я что то не понимаю(( Помогите пожалуйста |
#2
|
||||
|
||||
Видимо он хочет, чтобы хеш не каждый раз пересчитывался целиком, а применялась обратная операция для "вышедшего" из сравниваемого блока символа и потом применялся шаг хеширования к "добавившемуся".
jmp $ ; Happy End! The Cake Is A Lie. |
#3
|
|||
|
|||
Ну скорее всего так и есть..
Еще и формулу какую ту дал Код:
w:=d*(w-k*T[i-m])+T[i]; {вычисление нового значения w} |