많은 정규 표현식에 대한 문자열 검사

Question

길이가 인 입력 문자열 S가 인 경우를 고려하십시오. 응용 프로그램은 S가 m 정규 표현식 중 하나와 일치하는지 고려해야합니다. 관련된 특정 정규 표현식이 시간 (O) (n)에서 일치 할 수 있다고 가정하면 모든 표현식을 순차적으로 테스트하는 간단한 O (mn) 접근 방식보다 모든 m 표현식을 더 빨리 테스트 할 수 있습니까? 또한 이러한 작업이 가능하다면이를 구현하는 라이브러리 (언어)가 있습니까?

Answer 1

정말이 질문에 대한 답변이 확실하지 않습니다.

유효 문자열 목록과 유효하지 않은 문자열 목록을 테스트하고 특정 정규식을 테스트하는 데 사용할 수있는 그루비 스크립트입니다.

def validList = ["9999","[9999]","9-9","[9-9]","09XYAB","ABXY","BA09YX"] 
def invalidList = ["[999","9- ", "9-]", "9- 9","9[", "[999[", "09XYABC","1234", "A B"] 
def pattern = ~/([09XYAB-]*)|([\[]([09XYAB-]*)([\]]))/ 
print "Verifying against the regex '${pattern}'\n" 
print "Valid List Result(+ve tests)" 
print "\n---------------------------------------------\n" 
validList.each{ 
    if(pattern.matcher(it).matches()) { 
     print it +"\ttest passed - Pattern matched\n" 
    } else { 
     print it +"\ttest failed - Pattern not matched\n" 
    } 
} 
print "\n" 
print "inValid List Result(-ve tests)" 
print "\n---------------------------------------------\n" 
invalidList.each{ 
    if(!(pattern.matcher(it).matches())) { 
     print it +"\tTest Passed - Pattern not matched\n" 
    } else { 
     print it +"\tTest Failed - Pattern matched\n" 
    } 
} 

하나는 console

에 테스트 할 수 있습니다