317
правок
Изменения
Нет описания правки
==Псевдокод==
Функция поиска индекса первого вхождения сивола в массиве <tex>y</tex> с позиции <tex>\mathtt{fromIndex}</tex> до позиции <tex>\mathtt{toIndex}</tex>: '''int''' findFirst('''char'''[] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol):
'''for''' (i = fromIndex .. toIndex)
'''if''' (y[i] == symbol)
'''return''' -1
Проверка, что все символы в <tex>y</tex> с позиции <tex>fromIndex</tex> и до <tex>toIndex</tex> и <tex>x</tex> с начала и до конца совпадают.: '''boolean''' restEquals('''char'''[] y, '''int''' fromIndex, '''char'''[] x, '''int''' toIndex):
'''for''' (i = fromIndex .. toIndex)
'''if''' (y[i] != x[i - fromIndex])
'''return''' true
Стадия препроцессинга (совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]]): '''int'''[] preBmBc('''char'''[] x, '''int''' m) :
'''int'''[] result = '''int'''[ASIZE]
<font color=green>//Где ASIZE {{---}} размер алфавита</font>
'''return''' result
Основная стадия алгоритма: '''void''' RAITA('''char'''[] x, '''int''' m, '''char'''[] y, '''int''' n) :
'''int'''[] bmBc
'''char''' c, firstCh, middleCh, lastCh;
{| class = "wikitable"
! Изображение !! <tex>(j, bmBc[y[j]])</tex> !! Описание
|-align="centerleft"|[[Файл:Raita1.png|500px550px]]
|<tex>(7, 1)</tex>
|Делаем сравнение последних символов, оно неудачно, сдвигаемся.
|-align="centerleft"|[[Файл:Raita2.png|500px550px]]
|<tex>(8, 2)</tex>
|Последние символы совпали, сравниваем первые, сдвигаемся.
|-align="centerleft"|[[Файл:Raita3.png|500px550px]]
|<tex>(10, 2)</tex>
|Последние символы совпали, сравниваем первые, сдвигаемся.
|-align="centerleft"|[[Файл:Raita4.png|500px550px]]
|<tex>(12, 2)</tex>
|Совпали последний, первый и средний символы, пробегаемся по всему шаблону и сравниваем символы. Нашли строчку в тексте. Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся.
|-align="centerleft"|[[Файл:Raita5.png|500px550px]]
|<tex>(14, 1)</tex>
|Делаем сравнение последних символов, оно неудачно, сдвигаемся.
|-align="centerleft"|[[Файл:Raita6.png|500px550px]]
|<tex>(15, 8)</tex>
|Делаем сравнение последних символов, оно неудачно, сдвигаемся.
|-align="centerleft"|[[Файл:Raita7.png|500px550px]]
|<tex>(23, 2)</tex>
|Последние символы совпали, сравниваем первые, сдвигаемся. Строка закончилась, выхожим.
