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(n2)，其中n是原始表达式中的数字标记。