一个关于字符串搜索的问题

推荐学习书目

› 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

This topic created in 2710 days ago, the information mentioned may be changed or developed.

有一个长度为 50 万的字符串列表，现在要查找某个字符串是不是这些字符串的字串，找到所有符合的字符串. 我用 python 遍历实现了一遍，性能不太满足，各位有没有什么建议？

字符

字串

遍历

串

16 replies • 2019-06-06 14:24:26 +08:00

kirigaya

Jun 4, 2019

动态规划里的字符串查找？

goreliu

Jun 4, 2019 via Android

可以用 c 实现试试，如果性能还不行的话再用 kmp 优化下。直接在 python 优化可能效果不佳。

VDimos

Jun 4, 2019 via Android

你代码呢？

pmispig

Jun 4, 2019

你肯定用的单线程姿势吧，这个可以优化成多线程的

geelaw

Jun 4, 2019

字串 => 子串？

首先选择一个不出现在任何字符串里的一个字符 c，例如 c 选择 \0，然后把所有字符串接在一起 S = s1 \0 s2 \0 ... \0 sn，接着制作 S 的后缀树（线性时间），然后就可以很容易做你需要的事情了。

具体实现上，你不需要真的构造出 S 这个字符串，在制作后缀树的过程中可以 virtually 表示它。

hmzt

Jun 4, 2019

正则,应该比你自己写的快

testeststs

Jun 4, 2019

python 能没有现成的轮子？我不信。
没做过这么长的字符串，大概需要多少时间？

dongyx

Jun 4, 2019

不放设列表里有 n 个字符串，每个串长为 m。不管怎么做，第一次匹配都逃不了 O(nm)的时间复杂度。

如果你就匹配一次，直接用 KMP 挨个匹配就好，O(nm)。

如果你有多个模式串，要匹配多次，建议先把 n 个文本串建成一颗 Trie 树，建树的时间是 O(nm)，以后每次匹配的时间只需要 O(m)。

dongyx

Jun 4, 2019

不好意思，上面第二个方案说错了，是把 n 个文本串的所有后缀建成一颗 Trie 树，建树时间是 O(n * m^2)。