V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
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
cheesea
V2EX  ›  Python

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

  •  
  •   cheesea · 2018-05-10 12:42:12 +08:00 · 4355 次点击
    这是一个创建于 2139 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    12 条回复    2018-05-14 15:35:08 +08:00
    glasslion
        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 算法呢
    HelloAmadeus
        2
    HelloAmadeus  
       2018-05-10 12:53:23 +08:00 via Android
    难实现吧,而且也没什么必要,大部分程序的字符串处理都很短的
    watzds
        3
    watzds  
       2018-05-10 12:58:53 +08:00 via Android
    字符串不长的情况下,还不一定呢,而且最坏情况才是 mn,一般情况差不多
    sticnarf
        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) 的算法,但在大部分实际的情况下,最坏的情况极少发生。
    roy2220
        5
    roy2220  
       2018-05-10 13:01:16 +08:00 via Android
    因为这样做不对
    xomix
        6
    xomix  
       2018-05-10 13:41:46 +08:00   ❤️ 1
    因为合格的员工不会把千八百甚至上万的这种需求仍旧定义为简单的 find 需求,所以在这种情况下当然是朴素的算法更直接。
    josephpei
        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
    junnplus
        8
    junnplus  
       2018-05-10 14:58:13 +08:00
    首先提问题需要知道是什么,再问为什么,不要一上来就“据我所知”,然后扣高帽子 : )

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

    #4 正解
    josephpei
        9
    josephpei  
       2018-05-10 14:58:47 +08:00
    C++17 里还有 boyer_moore_horspool_searcher
    cheesea
        10
    cheesea  
    OP
       2018-05-10 18:16:43 +08:00
    @junnplus
    。。。。。。。。。。。。
    shiyouming91
        11
    shiyouming91  
       2018-05-11 05:22:19 +08:00 via iPhone
    据我所知,kmp 需要先花时间编译被找的字符串,在不知道被找的字符串是否会被重复使用的前提下效率只会更低。
    luzhongqiu
        12
    luzhongqiu  
       2018-05-14 15:35:08 +08:00
    被搜索的是常态的话,用 ac 自动机吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5852 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 03:32 · PVG 11:32 · LAX 20:32 · JFK 23:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.