我想要一种可以在Java中用于搜索字符串中的子字符串的高效算法（或库）。

我想做的是：

给定输入字符串 -INSTR ：

“ BCDEFGH”

以及一组候选字符串 -CAND ：

“ AB”，“ CDE”，“ FG”，“ H”，“ IJ”

在 INSTR中* 找到与子字符串匹配的任何 CAND 字符串 *

在此示例中，我将匹配“ CDE”，“ FG”和“ H”（但不匹配“ AB”和“ IJ”）

可能有成千上万个候选字符串（用CAND表示），但更重要的是，我将进行这种搜索数百万次，因此我需要使其快速。

我想使用char数组。另外，我也没有像分布式搜索那样对体系结构解决方案有足够的了解-只是在本地进行搜索的最有效的功能/算法。

另外，CAND和INSTR中的所有字符串都将相对较小（<50个字符），即目标字符串INSTR相对于候选字符串而言并不长。

*我应该提到的 *更新 是，CAND字符串的集合在INSTR的所有值上都是不变的。

更新 我只需要知道有一个比赛-我就不需要知道比赛是什么。

最终更新 由于实现的简单性，我选择尝试AhoCorsick和Rabin-Karp。因为我有可变长度的模式，所以我使用了一个经过修改的Rabin-
Karp，该哈希对每个模式的前n个字符进行了哈希处理，其中n是最小模式的长度，N则是我的滚动子字符串搜索窗口的长度。对于Aho
Corsick，我使用了这个

在我的测试中，我在两个文档的报纸文章中搜索了1000个模式，对1000个迭代进行了平均等。完成的标准化时间为：

AhoCorsick ：1

拉宾卡普 ：1.8

天真的搜索 （检查每个模式并使用string.contains）：50

*一些资源描述了以下答案中提到的算法：

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html

http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf

http://www-igm.univ-mlv.fr/~lecroq/string/index.html *