我想要一个有效的算法(或库),我可以在Java中使用它来搜索字符串中的子串.
我想做的是:
给定一个输入字符串 - INSTR:
"BCDEFGH"
还有一组候选字符串--CAND:
"AB","CDE","FG","H","IJ"
在INSTR中查找匹配为子字符串的任何CAND字符串
在这个例子中,我将匹配"CDE","FG"和"H"(但不是"AB"和"IJ")
可能有数千个候选字符串(在CAND中),但更重要的是,我将进行数百万次搜索,因此我需要它快速.
我想使用char数组.此外,我并不喜欢建筑解决方案,例如分发搜索 - 只是在本地进行搜索的最有效的功能/算法.
另外,CAND和INSTR中的所有字符串都将相对较小(<50个字符) - 即目标字符串INSTR相对于候选字符串不长.
我应该提到的更新,在所有INSTR值中,CAND字符串集是不变的.
更新我只需要知道有匹配 - 我不需要知道匹配是什么.
最终更新 由于实施简单,我选择尝试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