这是一个创建于 3362 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
pandachow 2015-09-09 10:39:05 +08:00
字符集多大？常见的中英文么？用 Wu Manber ：
http://webglimpse.net/pubs/TR94-17.pdf DNA 序列用 SBOM http://www-igm.univ-mlv.fr/~lecroq/string/bom.html |
|
3
pandachow 2015-09-09 11:09:02 +08:00
@Ixizi 如果你需要检测的字符串只有一个，用 Boyer-Moore 或者它的一个简化版本 Horspool 即可，多数浏览器，编辑器的 Ctrl (Cmd )+F 查找功能都是用它实现的。
大名鼎鼎的 KMP 也可以，不过它速度战五渣。 单字符串匹配基本有三种思路： 1. 挨个读字符，检查是否有匹配。代表算法是 KMP 和 Shift-Or 。 2. 构造一个滑动的窗口，然后一边滑动窗口，一边检查公共后缀。代表算法是 Boyer-Moore ，和它的一个著名的简化版本 Horspool 。 3. 也是构造窗口，但是搜索的最长后缀。模式串较短的话，用 BNDM ，较长的话，用 BOM 。 我只能帮你到这里了。 |
 |
4
wangleineo 2015-09-09 12:44:18 +08:00
弱弱问一句， KMP 和 Boyer-Moore 思路不是很相似吗？效率会有很大差别？
|
Select Language