Aho-Corasick算法的输出函数

Question

我在实现Aho-Corasick算法的输出函数时遇到了问题。一般来说，我不太理解输出函数是如何工作的。根据goto函数中的this paper，我将适当的模式索引放到输出中，就像失败函数中的output[currentState] = patternIndex;一样，我合并了状态S的现有输出和失败状态S的输出，就像搜索函数中的output[s] += output[fail[s]];一样，我使用了这样的条件：if (output[state]) != 0) then we find our pattern.，但这种方法不起作用，我得到了无意义的结果。也许，输出函数的伪代码在那篇论文中意味着其他东西，我不知道。

在大多数情况下，带有位映射的输出函数在大多数情况下也不能正常工作，我用的是here。错误的模式与此条件匹配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状态为最终状态，如下AC automation所示

输出函数表示您在当前状态下匹配的模式。像这样：

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)来计算哪个模式是匹配的。

这个操作就像one-hot编码。并且运算问题是输出函数的类型。如果输出函数类型是32位，那么我们只能搜索大多数31模式。因为在31模式上，它会因为移位而溢出。