418
правок
Изменения
м
Нет описания правки
Функция для вычисления таблицы суффиксов. Она находит для каждой позиции в шаблоне <tex>x</tex> максимальную длину суффикса <tex>x</tex>, который повторяется в строке и заканчивается в данной позиции. Например, для строки "'''abcabcabc'''" таблица будет '''0,0,3,0,0,6,0,0,9''', а для строки "'''abcabcc'''" - '''0,0,1,0,0,1,7'''. Также, очевидно, что значение функции для последнего элемента будет равно длине всей строки.
int[] '''suffixes'''(string x, int m):
int f; int suff[m]; suff[m - 1] = m; int g = m - 1; '''for ''' i = m - 2 .. 0 '''if (''' i > g and suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; '''else''' '''if ''' (i < g) g = i; f = i; '''while (''' g >= 0 and x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; return suff;
Функция для вычисления сдвигов хороших суффиксов
int i, j, suff[XSIZE];
int bmGs[]
suff = suffixes(x, m);
for (i = 0; i < m; ++i)
bmGs[i] = m;
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
* В лучшем случае требует <tex>O(n / m)</tex> сравнений.
где <tex>n</tex> {{---}} длина исходного текста, <tex>m</tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.
В 1991 году Р.Коул доказал следующую теорему:
==Ссылки==
* [http[wikipedia://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0 :Алгоритм_Бойера_—_Мура|Википедия:{{---}} Алгоритм Бойера-Мура]]* [http[wikipedia://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0_%E2%80%94_%D0%A5%D0%BE%D1%80%D1%81%D0%BF%D1%83%D0%BB%D0%B0 :Алгоритм_Бойера_—_Мура_—_Хорспула|Википедия:{{---}} Алгоритм Бойера-Мура-Хорспула]]* [http[wikipedia://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm Boyer–Moore_string_search_algorithm|Wikipedia:{{---}} Boyer–Moore string search algorithm]]
* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 Boyer-Moore algorithm]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
