Изменения
Нет описания правки
'''Алгоритм Райта''' {{- --}} алгоритм поиска подстроки в строке, который опубликовал Тим Райта в 1991 году, являющийся модификацией [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]] и улучшающий его асимптотику
==Описание алгоритма==
Алгоритм Райта ищет образец <tex>x</tex> в заданном тексте <tex>y</tex> сравнивания их символы. Сравнение происходит в следующем порядке (окном текста <tex>y</tex> будем называть последовательность символов <tex>i \dots m - i + 1</tex>, где <tex>m</tex> {{---}} длина образца <tex>x</tex>):
# '''Последний''' символ образца сравнивается с самым '''правым''' символом окна.
# Если они совпадают, то '''первый''' символ сравнивается с самым '''левым''' символом окна.
# Если они опять совпали, то сравниваются символы, находящиеся по середине образца и окна.
Если все шаги прошли успешно, то начинаем сравнивать образец и текст посимвольно в обычном порядке, начиная с второго с конца символа. В противном случае, выполняем функцию сдвига плохого символа, которая обрабона в стадии препроцессинга. Эта функция аналогична той, которая была использована в фазе препроцессинга [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]].
==Псевдокод==
'''void''' RAITA('''char'''[] x, '''int''' m, '''char'''[] y, '''int''' n) {
'''int'''[] bmBc
'''char''' c, firstCh, middleCh, lastCh;
'''if''' (m == 0)
'''return'''
'''else if''' (m == 1) {
<font color=green>//Проверка на случай поиска вхождения одного символа</font>
'''int''' match = 0
'''while''' (match < n) {
match = findFirst(y, match, n - 1, x[0])
'''if''' (match != -1) {
'''print'''(match)
}
'''else'''
'''print'''(<font color=green>"No matches"</font>)
'''return'''
}
}
'''int''' findFirst('''char'''[] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol){
'''for''' (i = fromIndex .. toIndex){
'''if''' (y[i] == symbol){
'''return''' i
}
}
'''return''' -1
}
'''boolean''' restEquals('''char'''[] y, '''int''' fromIndex, '''char'''[] x, '''int''' toIndex){
'''for''' (i = fromIndex .. toIndex){
'''if''' (y[i] != x[i - fromIndex + 1]){
'''return''' false
}
}
'''return''' true
}
<font color=green> //Стадия препроцессинга</font>
'''int'''[] preBmBc('''char'''[] x, '''int''' m) {
'''int'''[] result = '''int'''[m]
'''for''' (i = 0 .. m - 1){
result[i] = m;
}
'''for''' (i = 0 .. m - 2){
result[x[i]] = m - i - 1;
}
'''return''' result
}
bmBc = preBmBc (x, m)
firstCh = x[0];
middleCh = x[m/2];
lastCh = x[m - 1];
<font color=green>//Поиск</font>
'''int''' j = 0
'''while''' (j <= n - m) {
c = y[j + m - 1]
'''if''' (lastCh == c && middleCh == y[j + m / 2] && firstCh == y[j] &&
restEquals(y, j + 1, x, j + m - 2)){
'''print'''(j)
'''return'''
}
j += bmBc[c];
}
'''print'''(<font color=green>"No matches"</font>)
}
==Асимптотика==
==Пример==
==Источники информации==
