生成儘可能好的正則表達式匹配

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