Презентация на тему Поиск подстрок

как needle (англ.В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ. «иголка»),

а строку, в которой ведётся поиск — как haystack (англ.В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). 

массив Т из N элементов и массив W из

M элементов, причем 0Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки совпадение с шаблоном.

в текст T=abcabaabcabca

Образец входит в текст только один раз,

со сдвигом S=3, индекс i=4.

с первым символом массива W, 3. совпадение → сравнить вторые

символы и так далее, 4. несовпадение → I:=I+1 и переход на пункт 2,
Условие окончания алгоритма: 1. подряд М сравнений удачны, 2. I+M>N, то есть слово не найдено.

Алгоритм прямого поиска

просмотр всегда начинается с первого символа образца и поэтому

может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени).

3. Информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

  
i++;   
j = 0;   
while((j < m) && (haystack[i

+ j] == needle[j]))
j++;
}
while ((j != m) && (i < n – m));

ИДЕЯ


Пусть алфавит D={0, 1, 2, 3, 4, 5,

6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

16 = 5*343+ 3*342 +14*34+ 16 = 200480

6, 7, 8, 9}
Пример. Пусть шаблон имеет вид W

= 3 1 4 1 5 Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.

23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=3 …
31415(mod 13)=7

срабатывание.
Из равенства ki= kj (mod q) не следует, что

ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W[1…m] и T[s+1…s+m] на самом деле.

затраты на анализ холостых срабатываний будут невелики.  В худшем случае

время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.

11, 13, 17. Пусть W={2 6}
26 mod 11=4 →

k =3 холостых срабатывания, 26 mod 13=0 → k =1 холостое срабатывание, 26 mod 17=9 → k =0 холостых срабатываний.