字符串正则表达式匹配的有效算法

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

就时间复杂性而言，这是最快的了。在

每个regex都有与每个字符串至少匹配一次。否则，您将无法获得“匹配”或“不匹配”的信息。在

就绝对时间而言，您可以使用^{}来避免慢Python循环：

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