我在实现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)此外，我不太明白为什么按位运算用于输出计算。
我将不胜感激在澄清输出函数实现方面的任何帮助。
编辑1：似乎，该问题在位移操作后溢出：output[currentState] |= (1 << i);和out[currentState] & (1 << j)到目前为止，尝试使用BigInteger，但似乎会导致性能问题。
EDIT2：尝试了BitSet，但性能仍然很差。也许，算法的实现存在问题，我不知道。
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模式中，它会通过移动而溢出。