給定一個RE，獲得最大的子字符串匹配

Question

我正在尋找一個位的代碼將：

Given regular expression E, derive the longest string X 
such that for every S, X is a substring of S iff S will match E 

例子：

E = "a", X = "a" 
E = "^a$", X = "a" 
E = "a(b|c)", X = "a" 
E = "[ab]", X = "" 

背景：我要匹配一些正則表達式僅支持子字符串搜索的數據存儲 。通過對數據存儲應用子串 來優化正則表達式搜索將會很好，以儘可能地減少傳輸的數據量 。

例子2：

如果我想趕上 「錯誤富」， 「錯誤酒吧」， 「錯誤巴茲」，我可能會指定

error: (foo|bar|baz) 

和發送

search "error: " 

到數據存儲，然後重新編譯返回的項目。

謝謝！

Answer 1

通常而言，您可以嘗試在所有非唯一（（a | b），[ab]）匹配處拆分正則表達式，然後查找結果數組中的最長字符串。像

$foo = longest(regex_split($regex, '(\(.*?\|.*?\))|(\[.*?\])')); 

Answer 2

東西也許RE轉換爲有限狀態自動機，並尋找需要存在於開始之間的路徑，並完成國家......有圖幾何思維可以更容易給你最長的部分，至少它是在我的情況。