Алгоритм Кнута-Морриса-Пратта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 15: Строка 15:
 
   }
 
   }
 
*'''Корректность работы'''
 
*'''Корректность работы'''
Отметим, что из-за символа <tex>\$</tex> значение <tex>\pi(k) \leq t</tex> для всех <tex>k</tex>.
+
  Отметим, что из-за символа <tex>\$</tex> значение <tex>\pi(k) \leq t</tex> для всех <tex>k</tex>.
По определению <tex>\pi()</tex>, если <tex>\pi(k) = t</tex>, то <tex>P[0..t - 1] = P[k - t + 1..k]</tex>, то есть <tex>T = S[k - t - t..k - t - 1]</tex>, то есть <tex>T</tex> входит в <tex>S</tex>, начиная с позиции <tex>k - t - t</tex>.
+
  По определению <tex>\pi()</tex>, если <tex>\pi(k) = t</tex>, то <tex>P[0..t - 1] = P[k - t + 1..k]</tex>, то есть <tex>T = S[k - t - t..k - t - 1]</tex>, то есть <tex>T</tex> входит в <tex>S</tex>, начиная с позиции <tex>k - t - t</tex>.
Пусть теперь <tex>T</tex> входит в <tex>S</tex>, начиная с позиции <tex>i</tex>. Тогда <tex>S[i..i + t - 1] = T[0..t - 1]</tex>. Иными словами, <tex>P[0..t - 1] = P[t + 1 + i..t + i + t]</tex>, что эквивалентно <tex>\pi(t + i + t) = t</tex>.
+
  Пусть теперь <tex>T</tex> входит в <tex>S</tex>, начиная с позиции <tex>i</tex>. Тогда <tex>S[i..i + t - 1] = T[0..t - 1]</tex>. Иными словами, <tex>P[0..t - 1] = P[t + 1 + i..t + i + t]</tex>, что эквивалентно <tex>\pi(t + i + t) = t</tex>.
 
*'''Время работы'''
 
*'''Время работы'''
<tex>O(s + t)</tex>(время подсчета <tex>\pi()</tex> для <tex>P</tex>) + <tex>O(s)</tex>(последующий <tex>for</tex>) <tex>= O(s + t)</tex>.
+
  <tex>O(s + t)</tex> (время подсчета <tex>\pi()</tex> для <tex>P</tex>) + <tex>O(s)</tex> (последующий <tex>for</tex>) <tex>= O(s + t)</tex>.
 +
*'''Оценка по памяти'''
 +
  Предложенная реализация имеет оценку по памяти <tex>O(S+T)</tex>. Оценки <tex>O(S)</tex> можно добиться за счет не запоминания значений <tex>pi()</tex> для позиций в <tex>P</tex> меньших <tex>t + 1</tex> (т.е. до начала цепочки <tex>S</tex>)

Версия 20:28, 27 июня 2011

Постановка задачи

Дана цепочка [math]S[/math] и образец [math]T[/math]. Требуется найти все позиции, начиная с которых [math]T[/math] входит в [math]S[/math].

Алгоритм решения

[math]t = |T|; s = |S|; \$[/math] - любой символ, не входящий в алфавит [math]S[/math] и [math]T[/math]

  • Псевдокод
 P = [math]T[/math] + '$' + [math]S[/math];
 <вычисление префикс-функции для цепочки P>
 count = 0
 for (i = 0 .. (s - 1)) {
   if ([math]\pi[/math](t + i + 1) == t) {
     answer[count] = i + 1 - t
     count = count + 1
   }
 }
  • Корректность работы
 Отметим, что из-за символа [math]\$[/math] значение [math]\pi(k) \leq t[/math] для всех [math]k[/math].
 По определению [math]\pi()[/math], если [math]\pi(k) = t[/math], то [math]P[0..t - 1] = P[k - t + 1..k][/math], то есть [math]T = S[k - t - t..k - t - 1][/math], то есть [math]T[/math] входит в [math]S[/math], начиная с позиции [math]k - t - t[/math].
 Пусть теперь [math]T[/math] входит в [math]S[/math], начиная с позиции [math]i[/math]. Тогда [math]S[i..i + t - 1] = T[0..t - 1][/math]. Иными словами, [math]P[0..t - 1] = P[t + 1 + i..t + i + t][/math], что эквивалентно [math]\pi(t + i + t) = t[/math].
  • Время работы
 [math]O(s + t)[/math] (время подсчета [math]\pi()[/math] для [math]P[/math]) + [math]O(s)[/math] (последующий [math]for[/math]) [math]= O(s + t)[/math].
  • Оценка по памяти
 Предложенная реализация имеет оценку по памяти [math]O(S+T)[/math]. Оценки [math]O(S)[/math] можно добиться за счет не запоминания значений [math]pi()[/math] для позиций в [math]P[/math] меньших [math]t + 1[/math] (т.е. до начала цепочки [math]S[/math])