최상의 정규 표현식 일치 생성

Question

주어진 정규 표현식 R, 예 : ^[a-z]+$ 및 일치하지 않는 문자열 예. abc-d@e, 일치하는 S의 가장 긴 하위 집합 (이 경우 abcde)을 어떻게 생성 할 수 있습니까?

저는 일반적인 솔루션에 관심이 있습니다. 예를 들어 R=/^[0-9]+(?=[a-z])/과 S=x123a에 대한 알고리즘은 123a을 반환해야합니다.

다른 말로하면 문제는 다음과 같습니다. 일치하지 않는 문자열에서 제거하여 일치시켜야하는 항목입니다.

Answer 1

내가 무력 솔루션 (자신의 정규식 엔진을 작성하지 않고, 가능) 만 생각 :

import itertools 
import re 

def all_substrings(s): 
    for i in reversed(range(len(s))): 
     for sequence in itertools.combinations(range(len(s)), i+1): 
      yield "".join(s[n] for n in sequence) 

def find_longest(s, regex): 
    for substring in all_substrings(s): 
     if regex.search(substring): 
      return substring 

print(find_longest("abc-d@e", re.compile(r"^[a-z]+$"))) 
print(find_longest("x123a", re.compile(r"^[0-9]+(?=[a-z])"))) 

출력 :

abcde 
123a