Лекция №16. Поиск подстрок. Предмет "Структуры и алгоритмы обработки данных"

  • View
    2.474

  • Download
    0

Embed Size (px)

Transcript

  • 1. . .. : . , www.grebenshikov.ru

2. : - ( ). . , - . . , , , -, . . , . 1 3. : T [1..n] P [1..m], m n. P T - . , P T s, 0 s n m T [s + 1..s + m] = P [1..m].: P - T .2 4. - , . - .xy - .w < x - w x, y , x = wy.w = x - w x, y , x = yw. 3 5. x, y, z - , - x = z y = z. |x| |y|, x = y. |x| |y|, y = x. |x| = |y|, x = y.4 6. NaiveStringMatcher(T, P ) 1 n length[T ] 2 m length[P ] 3 for s 0 to n m 4 do if P [1..m] = T [s + 1..s + m] 5 then print(s) 5 7. 6 8. - : T = an, P = amT (n) = ((n m + 1)m) m = n/2 T (n) = (n2)7 9. -: - - .h(S[1..k]) = (S[k] + d(S[k 1] + . . . + d(S[2] + dS[1]) . . .))mod q, d - , q - .8 10. -h(P [1..m]) - .{s : h(P [1..m]) = h(T [s..s + m]) 0 s n m} - - . ts = h(T [s..s + m]), ts+1 = (d(ts T [s + 1]g) + T [s + m + 1]) mod q, g dm1(mod q) 9 11. - 10 12. - 11 13. - h(P ) = ts , P = T [s..s + m]. s .12 14. 13 15. - T (n, m) = (m) + ((n m + 1)m).? T (n, m) = O(n) + O(m(v + n/q)), v - - q - -. v = O(1) q m T (n, m) = O(m + n) = O(n), nm 14 16. M = (Q, q0, A, , )Q - ,q0 Q - ,A Q - , - , - Q Q. 15 17. - .( ) = q0(wa) = ((w), a) w , a 16 18. (x) = max{k : Pk = x}, Pk < P |Pk | = k - , P = ab, ( ) = 0, (ccaca) = 1, (ccab) = 2. : 1. Q = {0, 1, . . . m}, q0 = 0, A = m 2. (q, a) = (Pq a) 17 19. P = ababaca18 20. - 19 21. 20 22. - - T (n, m) = O(m3||). - - T (n, m) = O(m||) - T (n, m) = (n) 21 23. . : --, -, ---, --,--, --. : -, , -, -. 22 24. . : , -, -. : ,, -. 23 25. ., ., ., . -: , 2- . - . : - , 2007. .1017-1046. , . -. - .: .. , 2006. , . , : . -.: ; -, 2003.24