java - 将字词列表与正则表达式列表进行比较的算法

我想计算来自expList的textToBeTested数组中单词的存在。

请注意，expList和textToBeTested数组都可能非常大。

我可以简单地遍历两个列表并使用“.matches”方法进行计数，但是它在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"};

例如在上面的textToBeTested数组中，“更好”和“我”与expList数组中的字符串匹配，因此它将返回2。

非常感谢您的帮助。

最佳答案

将您所有的模式编译为使用轮换的更大模式呢？如果将变更正确编译到状态机中，则变更可以很快(例如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++;
    }
}