![]() |
|||
Алгоритм Бойера-МураПусть даны некоторые строки Для построения таблицы сдвигов каждому символу поставим в соответствие число, которое равно минимальному количеству символов от него до конца строки (включая сам символ); всем символам, которые не содержатся в строке, ставим в соответствие В тривиальном алгоритме Реализация алгоритма построения таблицы на языке С++: std::vector<int> shifts(ALPHABET_SIZE, n2 + 1);
for (int i = 0; i < n2; i++) {
shifts[s2[i]] = n2 - i;
}
Сложность построения таблицы равна
![]() Рассмотрим теперь сам алгоритм:
Реализация алгоритма на языке С++: int shift = 0;
while (shift + n2 <= n1) {
int i = n2 - 1;
while (i >= 0 && s2[i] == s1[shift + i]) {
i--;
}
if (i < 0) {
return shift;
} else if (shift + n2 < n1) {
shift += shifts[s1[shift + n2]];
} else {
break;
}
}
В среднем сложность алгоритма равна
![]() ![]() ![]() ![]() ![]() ![]() |
|||
|
|||
|