怎么高效的检测一个字符串在大量字符串是否有同名的?

[Ixizi]

[pandachow]

字符集多大？常见的中英文么？用 Wu Manber ：

http://webglimpse.net/pubs/TR94-17.pdf

DNA 序列用 SBOM

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

[Ixizi]

@pandachow 英文比较难看懂啊…

[pandachow]

@Ixizi 如果你需要检测的字符串只有一个，用 Boyer-Moore 或者它的一个简化版本 Horspool 即可，多数浏览器，编辑器的 Ctrl (Cmd )+F 查找功能都是用它实现的。

大名鼎鼎的 KMP 也可以，不过它速度战五渣。

单字符串匹配基本有三种思路：
1. 挨个读字符，检查是否有匹配。代表算法是 KMP 和 Shift-Or 。
2. 构造一个滑动的窗口，然后一边滑动窗口，一边检查公共后缀。代表算法是 Boyer-Moore ，和它的一个著名的简化版本 Horspool 。
3. 也是构造窗口，但是搜索的最长后缀。模式串较短的话，用 BNDM ，较长的话，用 BOM 。

我只能帮你到这里了。

[wangleineo]

弱弱问一句， KMP 和 Boyer-Moore 思路不是很相似吗？效率会有很大差别？