Алгоритм Рабина - Карпа. Поиск подстрок сдвигом

Сентябрь 7, 2022

Главная
Алгебра
Алгоритм Рабина - Карпа. Поиск подстрок сдвигом

Содержание

2. Поиск подстрок сдвигом function NaiveSearch(string s[1..n], string sub[1..m]) for i from 1 to n for j
3. Вот так выглядит алгоритм (исходный код приложения) function RabinKarp(string s[1..n], string sub[1..m]) hsub := hash(sub[1..m]) hs
4. function RabinKarpSet(string s[1..n], set of string subs, m) { set hsubs := emptySet for each sub
5. Спасибо за внимание!
10. Скачать презентацию

Слайд 2

Поиск подстрок сдвигом
function NaiveSearch(string s[1..n], string sub[1..m]) for i from 1

to n for j from 1 to m if s[i+j-1] ≠ sub[j] jump to next iteration of outer loop return i
return not found

Слайд 3

Вот так выглядит алгоритм (исходный код приложения)
function RabinKarp(string s[1..n], string sub[1..m])

hsub := hash(sub[1..m]) hs := hash(s[1..m]) for i from 1 to (n-m+1) if hs = hsub if s[i..i+m-1] = sub return i hs := hash(s[i+1..i+m]) return not found

Слайд 4

function RabinKarpSet(string s[1..n], set of string subs, m) { set hsubs

:= emptySet
for each sub in subs
insert hash(sub[1..m]) into hsubs
hs := hash(s[1..m])
for i from 1 to n
if hs ∈ hsubs
if s[i..i+m-1] = a substring with hash hs return i
hs := hash(s[i+1..i+m])
return not found
}

Слайд 5

Спасибо за внимание!

Слайд 6

Слайд 7

Слайд 8