推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
Python 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢？
cheesea · 2018-05-10 12:42:12 +08:00 · 4574 次点击这是一个创建于 2400 天前的主题，其中的信息可能已经有所发展或是发生改变。
据我所知 python 的 str2 in str1, str1.find(str2)等操作，时间复杂度是 O(MN)，那么为什么不用效率更高的 KMP 算法呢？
 |
1
glasslion 2018-05-10 12:48:20 +08:00  1
Java 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢
C++ 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢 Javascript 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢 Ruby 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢 Go 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢 PHP 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢 |
 |
2
HelloAmadeus 2018-05-10 12:53:23 +08:00 via Android
难实现吧，而且也没什么必要，大部分程序的字符串处理都很短的
|
 |
3
watzds 2018-05-10 12:58:53 +08:00 via Android
字符串不长的情况下，还不一定呢，而且最坏情况才是 mn，一般情况差不多
|
 |
4
sticnarf 2018-05-10 12:59:48 +08:00 5
https://github.com/python/cpython/blob/master/Objects/stringlib/fastsearch.h#L5
介于 Boyer-Moore 和 Horspool 之间的算法，效率比 KMP 要高。 主流 C++标准库里的 find() 的确是朴素的 O(MN) 的算法，但在大部分实际的情况下，最坏的情况极少发生。 |
 |
5
roy2220 2018-05-10 13:01:16 +08:00 via Android
因为这样做不对
|
 |
6
xomix 2018-05-10 13:41:46 +08:00 1
因为合格的员工不会把千八百甚至上万的这种需求仍旧定义为简单的 find 需求，所以在这种情况下当然是朴素的算法更直接。
|
 |
7
josephpei 2018-05-10 14:56:32 +08:00
c++17 里新加了一个函数 boyer_moore_searcher : A searcher suitable for use with the Searcher overload of std::search that implements the Boyer-Moore string searching algorithm
|
 |
8
junnplus 2018-05-10 14:58:13 +08:00
首先提问题需要知道是什么，再问为什么，不要一上来就“据我所知”，然后扣高帽子 : )
kmp 在字符串搜索中并不是很高效的算法，另外算法的使用离不开场景... #4 正解 |
|
9
josephpei 2018-05-10 14:58:47 +08:00
C++17 里还有 boyer_moore_horspool_searcher
|
 |
11
shiyouming91 2018-05-11 05:22:19 +08:00 via iPhone
据我所知，kmp 需要先花时间编译被找的字符串，在不知道被找的字符串是否会被重复使用的前提下效率只会更低。
|
 |
12
luzhongqiu 2018-05-14 15:35:08 +08:00
被搜索的是常态的话，用 ac 自动机吧
|
Select Language