python - 高效的字符串算法——正则匹配

Question

问题陈述:

Given two list A of strings and B of regex's(they are string too).
For every regex in list B, find all the matching strings in list A.
Length of list A <= 10^6 (N)
Length of string B <= 100 (M)
Length of strings, regex <= 30 (K)
Assume regex matching and string comparisons take O(K) time and regex can contain any python regex supported operations.

我的算法:

for regex in B:
    for s in A:
        if regex.match(s):
            mapping[regex].add(s)

这需要 O(N*M*K) 时间。
有什么方法可以在牺牲空间(使用任何数据结构)的情况下提高时间效率吗？

Answer 1

就时间复杂度而言，这已经是最快的速度了。

每个正则表达式必须与每个字符串至少匹配一次。否则，您将无法获取“匹配”或“不匹配”的信息。

在绝对时间方面，你可以使用filter避免缓慢的 Python 循环:

mapping = {regex: filter(re.compile(regex).match, A) for regex in B}