297
правок
Изменения
→Процедура merge
'''Случай 3: A and B:''' В этом случае мы ничего не можем сказать о том, совпадают ли символы <tex>y[p]</tex> и <tex>x[p-i]</tex>, поэтому их надо сравнить.
Возвращаемся к процедуре merge. В случае 2, или если в случае 3 выявлено несовпадение символов, необходимо увеличить количество несовпадений символов <tex>b</tex> на единицу и обновить <tex>tm[i][b]</tex>. Соответствующими значениями таблицы для <tex>merge</tex> являются <tex>tm[i-r][1...t]</tex> и <tex>tm[r][q...k+1]</tex>. Переменные <tex>u</tex> и <tex>v</tex> в начале устанавливаются равными индексам первых элементов этих двух массововмассивов, соответственно, и последовательно увеличиваются.
Условия окончания работы процедуры следующие:
* Eсли Если <tex>b = k+1</tex>, то для случая, когда образц образец расположен относительно текста так, что <tex>x[1]</tex> совмещен с <tex>y[i+1]</tex>, обнаружено <tex>k+1</tex> несовпадение, поэтому из процедуры можно выйти.
* Bспомним, что самая правая из интересующих нас позиций в <tex>merge</tex>, а именно, <tex>j</tex>, равна <tex>r+tm[r][k+1]</tex>, если <tex>v = k+2</tex>, поэтому <tex>tm[r][k+1]</tex> будет уже использовано для предыдущего значения <tex>v</tex>, а именно, <tex>v = k+1</tex>, и поэтому позиция <tex>j</tex> должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры.
