推荐学习书目 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
这是一个创建于 2355 天前的主题，其中的信息可能已经有所发展或是发生改变。
有一个长度为 50 万的字符串列表，现在要查找某个字符串是不是这些字符串的字串，找到所有符合的字符串. 我用 python 遍历实现了一遍，性能不太满足，各位有没有什么建议？
 | 1 kirigaya 2019-06-04 13:59:27 +08:00 动态规划里的字符串查找？ |
 | 2 goreliu 2019-06-04 14:02:03 +08:00 via Android 可以用 c 实现试试，如果性能还不行的话再用 kmp 优化下。直接在 python 优化可能效果不佳。 |
 | 3 VDimos 2019-06-04 14:11:19 +08:00 via Android 你代码呢？ |
 | 4 pmispig 2019-06-04 14:17:00 +08:00 你肯定用的单线程姿势吧，这个可以优化成多线程的 |
 | 5 geelaw 2019-06-04 14:17:47 +08:00 字串 => 子串？ 首先选择一个不出现在任何字符串里的一个字符 c，例如 c 选择 \0，然后把所有字符串接在一起 S = s1 \0 s2 \0 ... \0 sn，接着制作 S 的后缀树（线性时间），然后就可以很容易做你需要的事情了。 具体实现上，你不需要真的构造出 S 这个字符串，在制作后缀树的过程中可以 virtually 表示它。 |
 | 6 hmzt 2019-06-04 14:20:25 +08:00 正则,应该比你自己写的快 |
 | 7 testeststs 2019-06-04 14:23:52 +08:00 python 能没有现成的轮子？我不信。 没做过这么长的字符串，大概需要多少时间？ |
 | 8 dongyx 2019-06-04 17:27:35 +08:00 不放设列表里有 n 个字符串，每个串长为 m。不管怎么做，第一次匹配都逃不了 O(nm)的时间复杂度。 如果你就匹配一次，直接用 KMP 挨个匹配就好，O(nm)。 如果你有多个模式串，要匹配多次，建议先把 n 个文本串建成一颗 Trie 树，建树的时间是 O(nm)，以后每次匹配的时间只需要 O(m)。 |
| 9 dongyx 2019-06-04 17:31:40 +08:00 不好意思，上面第二个方案说错了，是把 n 个文本串的所有后缀建成一颗 Trie 树，建树时间是 O(n * m^2)。 |
 | 10 HelloAmadeus OP @geelaw 是子串，不好意思搞错了。后缀树研究过一点，不确定好不好用，试一下实现一个 |
| 11 HelloAmadeus OP @dongyx 是多次匹配，trie 树考虑过，内存占用不能接受 |
 | 12 kedadiannao220 2019-06-05 09:19:26 +08:00 sed awk |
 | 14 bnbdfg 2019-06-05 11:36:23 +08:00 50 万长度，python 不太好实现你这种性能要求 |
 | 15 BiteTheDust 2019-06-05 11:55:55 +08:00 用后缀自动机可以很简单的实现 |
 | 16 longchisihai 2019-06-06 14:24:26 +08:00 试试看 flashtext |
Select Language