주어진 패턴이 Regex에 의해 생성되는지 검사하십시오.

Question

정규식과 일치 할 패턴 문자열이 있습니다. 패턴이 인 정규식에 의해 생성 된 유효한 문자열인지 확인해야합니다.

이제 질문 때문에 정규식은 '*'문자 및 사전 정의 된 편지 세트 (A-Z)를 만 포함 할 수 있습니다 흥미가된다. 여기

'*'는 의미가 있습니다 :

if regex is "a*": its closure { '','a','aa','aaa',.. } 
if its "ab*c" : its closure { 'ac','abc','abbc', ... } 

지금, 모든 가능성을 확인 그것에 되돌아 솔루션이있다.

나는 we only have " * " as a special symbol 이후로 우리가 더 복잡한 것으로 할 수 있는지 궁금합니다.

Answer 1

더 나은 복잡성을 수행 할 수 있습니까?

예. 백 트래킹을 생략하면, 필요하지 않은 번갈아 가며 할 수 있습니다. 받는 사람에 대하여 (선형 복잡성으로 수행 할 수 있습니다 X*

이에 XX*

변화에 X*X*의 모든 발행 수를 X*X의

1. 변화 모든 발행 수 : 만 당신은 당신의 정규 표현식에 정상화해야합니다 정규식 길이); 그럼 당신은 그냥 단일 패스 (입력 길이에 관한 선형 복잡성과 함께) 입력 문자열을 반복 수 있습니다.