regex - 如何测试字符串是否是任何正则表达式实例的子字符串？

Question

在任何编程语言和库中，

如何测试字符串是否是正则表达式任何实例的子字符串？

例如，正则表达式的所有实例

RA = /^a{1,2}c{1,2}$/

是

'ac', 'acc', 'aac', 'aacc'.

字符串 'cc' 不是正则表达式的一个实例，而是两个正则表达式实例的子字符串。你怎么能测试'c'有这样的属性？

等效地，您如何（通常）获得一个正则表达式，其实例都是另一个正则表达式的任何实例的子字符串。

对于上面的示例，正​​则表达式

RB = /^a{0,2}c{0,2}$/

有实例

'', 'c', 'cc', 'a', 'ac', 'acc', 'aa', 'aac', 'aacc'

它们是 RA 实例的所有子串。

对于任何正则表达式 RA，您如何从 RA 计算这样的 RB？

提前致谢！

Answer 1

如果您的意思是计算机科学正则表达式，您可以通过形成所有标记子序列的交替来做到这一点：

/^a{1,2}c{1,2}$/ -> /^(a{1,2}|a{1,2}c{1,2}|c{1,2}|)$/

请注意，长度将增长为 O(n ² )，其中 n 是原始表达式中的数字标记。