단어 문자열 목록을 정규 표현식 목록과 비교하는 알고리즘

Question

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. 어떤 도움 주셔서 대단히 감사합니다 반환합니다.

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++; 
    } 
}