соответствие строки бойер мур .. количество символов

Question

во многих примерах использования алгоритма Бойера Мура, есть объявление 256 символов, я не знаю, для чего это число указывает ... пожалуйста, помогите

Пример из (https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm ):

function preprocess(pattern)
    T ← new table of 256 integers
    for i from 0 to 256 exclusive
        T[i] ← length(pattern)
    for i from 0 to length(pattern) - 1 exclusive
        T[pattern[i]] ← length(pattern) - 1 - i
    return T

Answer 1

Указывается, что в алфавите есть 256 символов.

Этот предел в один байт прекрасно работает для ASCII. Но если вам нужен Unicode, вам также понадобится больше места в таблице T. Фактически, эта пространственная зависимость необходима для анализа алгоритма.

Как говорится в статье в Википедии:

Алгоритм меняет пространство на время, чтобы получить средний случай сложность O(n) для произвольного текста, хотя в худшем случае она равна O(nm), где длина шаблона m и длина строки поиска n.

Бойер-Мур в среднем O(n+m), так что теоретически это быстрее. В лучшем случае они одинаковы, а в патологических случаях BMH может go сорваться с рельсов больше, чем BM. Но на практике реализация Бойера-Мура-Хорспула происходит быстрее, потому что он использует пространство с умом. Что возвращает нас к этому столу T.

Таблица фиксированных размеров вышла из моды. Вы, вероятно, использовали бы dict или HashMap или любой другой язык, который у вас есть под рукой.

Это значительно снижает стоимость таблицы в случае захвата всех символов Юникода , Фактически, это сокращает использование пространства с O(v) до O(min(v, n+m)).

Просто будьте осторожны, используйте структуру данных, поддерживаемую ha sh, чтобы случайно не добавить некоторый фактор log(v) ( или хуже) во время выполнения.