108
правок
Изменения
Новая страница: «==Постановка задачи== Дана цепочка <tex>S</tex> и образец <tex>T</tex>. Требуется найти все позиции, на…»
==Постановка задачи==
Дана цепочка <tex>S</tex> и образец <tex>T</tex>. Требуется найти все позиции, начиная с которых <tex>T</tex> входит в <tex>S</tex>.
==Алгоритм решения==
<tex>t = |T|; s = |S|; \$</tex> - любой символ, не входящий в алфавит <tex>S</tex> и <tex>T</tex>
*'''Псевдокод'''
P <- <tex>T</tex> + '$' + <tex>S</tex>;
<вычисление префикс-функции для цепочки P>
count <- 0
for (i = 0..s - 1) {
if (<tex>\pi</tex>(t + i + 1) = t) {
answer[count] <- i + 1 - t
count <- count + 1
}
}
*'''Корректность работы'''
Отметим, что из-за символа <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>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>S</tex> и образец <tex>T</tex>. Требуется найти все позиции, начиная с которых <tex>T</tex> входит в <tex>S</tex>.
==Алгоритм решения==
<tex>t = |T|; s = |S|; \$</tex> - любой символ, не входящий в алфавит <tex>S</tex> и <tex>T</tex>
*'''Псевдокод'''
P <- <tex>T</tex> + '$' + <tex>S</tex>;
<вычисление префикс-функции для цепочки P>
count <- 0
for (i = 0..s - 1) {
if (<tex>\pi</tex>(t + i + 1) = t) {
answer[count] <- i + 1 - t
count <- count + 1
}
}
*'''Корректность работы'''
Отметим, что из-за символа <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>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>.
