Python 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢？

[cheesea]

据我所知 python 的 str2 in str1, str1.find(str2)等操作，时间复杂度是 O(MN)，那么为什么不用效率更高的 KMP 算法呢？

[glasslion]

Java 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢
C++ 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢
Javascript 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢
Ruby 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢
Go 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢
PHP 判断 str1 是否 str2 子串，为什么不用 KMP 算法呢

[HelloAmadeus]

难实现吧，而且也没什么必要，大部分程序的字符串处理都很短的

[watzds]

字符串不长的情况下，还不一定呢，而且最坏情况才是 mn，一般情况差不多

[sticnarf]

https://github.com/python/cpython/blob/master/Objects/stringlib/fastsearch.h#L5

介于 Boyer-Moore 和 Horspool 之间的算法，效率比 KMP 要高。

主流 C++标准库里的 find() 的确是朴素的 O(MN) 的算法，但在大部分实际的情况下，最坏的情况极少发生。

[roy2220]

因为这样做不对

[xomix]

因为合格的员工不会把千八百甚至上万的这种需求仍旧定义为简单的 find 需求，所以在这种情况下当然是朴素的算法更直接。

[josephpei]

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

[junnplus]

首先提问题需要知道是什么，再问为什么，不要一上来就“据我所知”，然后扣高帽子 : )

kmp 在字符串搜索中并不是很高效的算法，另外算法的使用离不开场景...

#4 正解

[josephpei]

C++17 里还有 boyer_moore_horspool_searcher

[cheesea]

@junnplus
。。。。。。。。。。。。

[shiyouming91]

据我所知，kmp 需要先花时间编译被找的字符串，在不知道被找的字符串是否会被重复使用的前提下效率只会更低。

[luzhongqiu]

被搜索的是常态的话，用 ac 自动机吧