Главная Промышленная автоматика.

Рис. 9.12. Скелетная машина.

нений состояния). My имеет то же множество состояний, что и скелетная машина. Поэтому состояние / машины My соответствует префиксу bibi. . bj цепочки-образа у.

My начинает работу в состоянии О и с входным указателем на Ci, т. е. на первый символ цепочки-текста x=aia2. .Оп- Если ai= -bi, то My переходит в состояние 1 и сдвигает входной указатель на вторую позицию цепочки-текста. Если ОгфЬи то М остается в состоянии О и сдвигает входной указатель на вторую позицию.

Допустим, что My после прочтения flifla- • -flft находится в состоянии /. Это означает, что последние / символов цепочки aifla- • .flft совпадают с biba- • -bj, а последние т символов в fliOa. . .а не являются префиксом цепочки Ьфг. . .bi для /п>/. Если а+и т. е. следующий входной символ, совпадает с bj+u то My переходит в состояние /+1 и сдвигает входной указатель на flft+a. Если aft+i=#=fc+i, то My переходит в наибольшее состояние i, для которого biba. . .bt - суффикс цепочки flifla- - .flft+i-

Чтобы облегчить нахождение состояния i, с машиной My связывается функция f, принимающая целочисленные значения. Она называется функцией отказов и задается так: / (j) - наибольшее число s</, для которого Ма- • -Ьа - суффикс цепочки biba. . .bj, т. е. bibi- .bg=bj-g+ib}.,+». . .bj. Если такого sl нет, то f(i)=0.

Пример 9.7. Пусть y=aabbaab. Функция f принимает значения

fit)

Например, /(6)=2, ибо аа - самый длинный собственный префикс цепочки aabbaa, который является ее суффиксом. □

Алгоритм вычисления функции отказов мы изложим несколько позже. Сейчас, чтобы увидеть, как функция отказов используется машиной My, определим функцию /"(/)=

1) /"(/)=/О"),

2) /»(/)=/(/"-"(У)) для т>1.

Иными словами, /""(/) - эта та же функция /, примененная т раз к /. (В примере 9.7 /"(6)=!.)

Снова предположим, что My после прочтения aiCa. . .flft находится в состоянии / и afc+i76/+i. В этот момент My итерирует



применение функции отказов к / до тех пор, пока не обнаруживается наименьшее значение т, для которого либо

1) и aft-n=b„+i, либо

2)/*»(/)=0 и апхфЬи

Таким образом. My движется назад через состояния /*(/). /"*(/), ... до тех пор, пока не встретит такое т, что условие 1 или 2 будет выполнено для /*">(/). но не для /""О)- Если выполнилось условие 2, то My переходит в состояние 0. В любом случае входной указатель сдвигается на flft+a.

В случае 1 легко проверить, что поскольку fcifcj. . .bj - самый длинный префикс цепочки у, который являлся суффиксом цепочки uiui. -cih, то bibi. . .bf(")(/)+i - самый длинный префикс цепочки у, который является суффиксом цепочки aifla- • -flft+i- В случае 2 никакой префикс цепочки у не является суффиксом цепочки Cifla- • • . . .flft+i.

Затем My обрабатывает входной символ а+г и продолжает работать по такой схеме до момента, когда либо попадет в заключительное состояние / (и тогда / последних просмотренных входных символов образуют вхождение цепочки y=bibi. . .bi), либо обработает последний входной символ из jc и не попадет в состояние / (и тогда у не является подцепочкой цепочки х).

Пример 9.8. Пусть y=aabbaab. Машина идентификации цепочек My изображена на рис. 9.13. Штриховые стрелки указывают значения функции отказов для всех состояний. На входе х= =abaabaabbaab машина My пройдет через такую последовательность состояний:

Вход: abaabaabbaab

Состояние: 0101231234567 О О

Например, вначале машина My находится в состоянии 0. Прочитав первый символ из х, она переходит в состояние 1. Так как из состояния 1 нет перехода по второму входному символу Ь, то My переходит в состояние О, т. е. в значение функции отказов для состояния 1, при этом входной указатель не сдвигается. Так как первый символ в у отличен от fc, то выполнено условие 2, и My остается в состоянии О и сдвигает входной указатель на позицию 3.

Рис. 9.13. Машина идентификации цепочек.



После прочтения двенадцатого входного символа My попадает в заключительное состояние 7. Таким образом, дойдя до позиции 12 в цепочке х, машина My нашла вхождение цепочки-образа у. □

Функцию / можно итеративно вычислить почти по той же схеме, по какой работает My. По определению /(1)=0. Допустим, что вычислены /(1), /(2) , /(/). Пусть f(j)=i. Чтобы вычислить /(/+

+ 1), исследуем b}+i и bt+i. Если bj+i=bt+u то f(J+l)=f{j)+l, поскольку

• •bibii = bj.iibj.ii.. .bj.1. Если bj+ibi+i, то находим наименьшее т, для которого либо

1) РЩ)=и и fc/+i=fc„+i, либо

2) /<»(/)=0 и bjibi.

В случае 1 полагаем /(/-М)=«-М. В случае 2 полагаем/(/+1)= =0. Детали даны в следующем алгоритме.

Алгоритм 9.2. Вычисление функции отказов

Вход. Цепочка-образ i/=M«- • -bi, Il.

Выход. Функция отказов / для у.

Метод. Выполнение программы на рис. 9.14. □

Пример 9.9. Рассмотрим поведение алгоритма 9.2 на входе у= =aabbaab. Формирование начальных данных дает /(1)=0. Поскольку fca=6i, то /(2)=1. Но ЬяфЬг и ЬзФЬи так что/(3)=0. Продолжая в том же духе, получаем значения f, указанные в примере 9.7. □

Докажем, что алгоритм 9.2 правильно вычисляет / за время 0(\у\). Сначала докажем корректность алгоритма.

begin

1. /(1).-0;

2. for /-2 until / do

begin

3. t -f(/-l);

4. while bjbi+i и f>0 do i*-f(i);

5. if bfbi+i и i = 0 then/(/)-0

6. else f{j)*-i + l end

Рис. 9.14. Вычисление функции отказов.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 [119] 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0046