给定一个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转换为有限状态自动机，并寻找需要存在于开始之间的路径，并完成国家......有图几何思维可以更容易给你最长的部分，至少它是在我的情况。