59
правок
Изменения
→Пример
[[Файл:Apostolico-Crochemore-Shifts.png]]
Примечание: <tex>v</tex> {{---}} помеченный бордер строки <tex>u</tex>.
Пусть теперь <tex>l = 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x = a ^ l bu</tex>, где <tex>a \in \Sigma</tex>, <tex>b \in \Sigma</tex>, <tex>a \neq b</tex>, <tex>u \in \Sigma^*</tex>). При каждой подстановке шаблона к тексту к позиции <tex>i</tex> мы проводим следующие сравнения: <tex>x[l] = y[i + l], x[l + 1] = y[i + l + 1], \ldots , x[m - 2] = y[i + m - 2], x[m - 1] = y[i + m - 1],</tex><tex> x[0] = y[i], x[1] = y [i + 1], \ldots , x[l - 1] = y[i + l - 1]</tex>.
Во время поиска вхождений мы рассматриваем данную тройку <tex>(i, j, k)</tex> где:
* <tex>0 \leqslant k \leqslant l</tex> и <tex>x[0, \ldots, k - 1] = y[j, \ldots , j + k - 1]</tex>
* <tex>l \leqslant i < m</tex> и <tex>x[l, \ldots, i - 1] = y[j + l, \ldots , i + j - 1]</tex>
(см. рисунок ниже)
Вначале инициализируем эту тройку <tex>(l, 0, 0)</tex>.
Теперь опишем, как по уже вычисленной тройке <tex>(i, j, k)</tex> перейти к следующей.
'''int''' k = 0
'''while''' j <tex>\leqslant</tex> y.size - x.size
'''while''' i < x.size '''and''' x[i] == y[i + j] <font color=green>// если <tex>x[i] = y[i + j]</tex></font> ++i <font color=green>// тогда следующая тройка <tex>(i + 1, j, k)</tex></font>
'''if''' i <tex>\geqslant</tex> x.size
'''while''' k < l '''and''' x[k] == y[j + k]<font color=green>// если <tex>k < l</tex> и <tex>x[k] = y[j + k]</tex></font> ++k <font color=green>// тогда следующая тройка <tex>(i, j, k + 1)</tex></font> '''if''' k <tex>\geqslant</tex> l <font color=green>// если <tex>k = l</tex></font> v.pushBack(j) <font color=green>// тогда найдена подстрока в позиции j</font> j += i - t[i] <font color=green>// вычисляем новый сдвиг</font>
'''if''' i == l
k = max(0, k - 1)<font color=green>// если <tex>i = l</tex> и <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex></font>
'''else'''
'''if''' t[i] <tex>\leqslant</tex> l <font color=green>// если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex></font>
k = max(0, t[i])
i = l
'''else''' <font color=green>// если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex></font>
k = l
i = t[i]
|[[Файл:Apostolico-Crochemore-step-1.png|500px]]
|<tex>(1, 0, 0)</tex>
|step Подставив шаблон к позиции <tex>0</tex> получим, что <tex>x[1] \neq y[1]</tex>. Вычислив сдвиг, получим <tex>j = 1</tex>.
|-align="center"
|[[Файл:Apostolico-Crochemore-step-2.png|500px]]
|<tex>(1, 1, 0)</tex>
|step 2Подставив шаблон к позиции <tex>1</tex> получим, что <tex>x[0, \ldots , 3] = y[1, \ldots , 4]</tex>. Следовательно, <tex>x</tex> подстрока <tex>y</tex> в позиции <tex>1</tex>. Вычислив сдвиг, получим <tex>j = 4</tex>.
|-align="center"
|[[Файл:Apostolico-Crochemore-step-3.png|500px]]
|<tex>(1, 4, 1)</tex>
|step 3Подставив шаблон к позиции <tex>4</tex> получим, что <tex>x[1] \neq y[5]</tex>. Вычислив сдвиг, получим <tex>j = 5</tex>.
|-align="center"
|[[Файл:Apostolico-Crochemore-step-4.png|500px]]
|<tex>(1, 5, 0)</tex>
|step 4Подставив шаблон к позиции <tex>5</tex> получим, что <tex>x[1] \neq y[6]</tex>. Вычислив сдвиг, получим <tex>j = 6</tex>.
|-align="center"
|[[Файл:Apostolico-Crochemore-step-5.png|500px]]
|<tex>(1, 6, 0)</tex>
|step 5Подставив шаблон к позиции <tex>6</tex> получим, что <tex>x[1] \neq y[7]</tex>. Вычислив сдвиг, получим <tex>j = 7</tex>.
|-align="center"
|[[Файл:Apostolico-Crochemore-step-6.png|500px]]
|<tex>(1, 7, 0)</tex>
|step 6Подставив шаблон к позиции <tex>7</tex> получим, что <tex>x[1] \neq y[8]</tex>. Вычислив сдвиг, получим <tex>j = 8</tex>.
|-align="center"
|[[Файл:Apostolico-Crochemore-step-7.png|500px]]
|<tex>(1, 8, 0)</tex>
|step 7Подставив шаблон к позиции <tex>8</tex> получим, что <tex>x[0, \ldots , 3] = y[8, \ldots , 11]</tex>. Следовательно, <tex>x</tex> подстрока <tex>y</tex> в позиции <tex>8</tex>.
|-
|}
