Функция вывода для алгоритма Aho-Corasick

Question

У меня проблема с реализацией функции вывода для алгоритма Aho-Corasick. В общем, я не совсем понимаю, как работает функция вывода. В соответствии с этой статьей в функции goto я помещаю соответствующий индекс шаблона для вывода, например output[currentState] = patternIndex;в функции сбоя я объединяю существующий вывод для состояния S с выводом для сбойного состояния S, например output[s] += output[fail[s]]; в функции поиска я использую такое условие: if (output[state]) != 0) then we find our pattern. Но такой подход не работает, и я получил глупый результат. Возможно, псевдокод для функции вывода означает что-то еще в этой статье, я не знаю.

Функция вывода с побитовым отображением, которая у меня здесь, также не работает правильно в большинстве случаев. Неправильные шаблоны соответствуют этому условию if ((output[currentState] & (1 << j)) != 0)Кроме того, я не совсем понимаю, почему побитовые операции используются для вычисления выхода.

Буду благодарен за любую помощь в разъяснении реализации функции вывода.

EDIT1: кажется, что проблема была в переполнении после операции сдвига битов: output[currentState] |= (1 << i);а также out[currentState] & (1 << j)Пока что пытался использовать BigInteger, но, похоже, это вызывает проблемы с производительностью.

EDIT2: пробовал BitSet, но производительность все еще очень плохая. Может быть, есть проблема в реализации алгоритма, я не знаю.

Answer 1

32-битная битовая операция, как показано ниже

шаблон: he, she, his, hers

input: shethehishetheehershehehishe

Общее состояние номер 9, а также 2, 5, 7, 9 состояние является конечным состоянием, как показано ниже автоматизации переменного тока

Выходная функция представляет собой шаблон, который вы сопоставили в текущем состоянии. лайк:

out[2] = he, out[5] = she/he, out[7] = his, out[9] = hers

The code "out[currentState] |= (1 << i)" just like below 

out[2] = 0000 0000 0000 0000 0000 0010 <-- means number 1(he) pattern matched 

out[5] = 0000 0000 0000 0000 0000 0110 <-- means number 1(he) and number 2(she) matched

так что пользуйтесь output[currentState] & (1 << j) рассчитать, какой шаблон соответствует.

Эта операция, как горячая кодировка. И проблема операции - тип выходной функции. Если тип выходной функции 32 биты, и мы можем просто искать не более 31 узоры. Потому что над 31 шаблоны, он будет переполнен смещением.