将字符串列表与正则表达式列表进行比较的算法

Question

我想从expist中计算textToBeTested数组中单词的存在情况。

请注意，expList和texttobetesting数组都可以非常大。

我可以简单地遍历两个列表并使用"。匹配"方法计数，但它是在O(n^2)。

是否有更快的算法或实现我可以使用?

    String[] expList = {"i", "i'd", "i'll", "i'm", "i'm", "bet[a-zA-Z]*", "my[a-zA-Z]*"};
    String[] textToBeTested = {"this", "is", "better", "than", "my", "method"};

。在上面的texttobetesting数组中，"better"one_answers"my"与expList数组中的字符串匹配，因此它将返回2。

非常感谢您的帮助

Answer 1

如何将所有模式编译成使用交替的更大模式?如果正确地编译成状态机，那么可以很快(像Aho Corasick或KMP)。

boolean first = true;
StringBuilder sb = new StringBuilder();
for (String s : expList) {
    sp.append("(?:").append(Pattern.quote(s)).append(')');
    if (!first) {
        sb.append('|');
    }
    first = false;
}
Pattern pattern = Pattern.compile(sb.toString());
// Possibly make this a ForkJoinTask
int count = 0;
for (String s : textToBeTested) {
    if (pattern.matcher(s).matches()) {
        count++;
    }
}