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

[HelloAmadeus]

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

[kirigaya]

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

[goreliu]

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

[VDimos]

你代码呢？

[pmispig]

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

[geelaw]

字串 => 子串？

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

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

[hmzt]

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

[testeststs]

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

[dongyx]

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

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

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

[dongyx]

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

[HelloAmadeus]

@geelaw 是子串，不好意思搞错了。后缀树研究过一点，不确定好不好用，试一下实现一个

[HelloAmadeus]

@dongyx 是多次匹配，trie 树考虑过，内存占用不能接受

[kedadiannao220]

sed
awk

[azh7138m]

@hmzt 字母大量重复的场景下，正则的性能就很低（

[bnbdfg]

50 万长度，python 不太好实现你这种性能要求

[BiteTheDust]

用后缀自动机可以很简单的实现

[longchisihai]

试试看 flashtext