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

Question

在任何编程语言和库中，

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

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

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

are

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

字符串“cc”不是正则表达式的实例，但它是两个正则表达式的子字符串。如何测试“c”具有此属性？

同样，如何获得（通常情况下）一个正则表达式，其实例都是另一个正则表达式的任意实例的子字符串。

对于上面的示例，使用以下正则表达式即可：

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

具有实例

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

这些实例的所有子字符串都是RA的子串。

如何从任何正则表达式RA中计算出这样的RB？

提前致谢！

- roy

---

你是指计算机科学中定义的正则表达式，还是大多数现代语言实现的（不规则）正则表达式？如果你指的是后者，那么你最感兴趣的是哪种语言？ - Mark Byers

我最感兴趣的是C++实现，但其他任何编程语言都可以。 - roy

Answer 1

如果您指的是计算机科学中的正则表达式，您可以通过形成所有令牌子序列的交替来实现此操作：

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

请注意，长度将随着原始表达式中标记数量的增加而呈O(n²)增长。

- Mark Byers

---

好的，这是一个非常好的答案。但是你知道一个正则表达式库实现了那种交替吗？如果不知道，你会选择哪个免费库来修改和实现它？ - roy

我从未听说过有任何库实现了这个功能，而且我怀疑如果性能是一个问题的话，正确地实现它对于一般情况来说将会非常困难。我猜想，如果你能将正则表达式转换为相应的有限状态机，那么你可能会得到一个更有效的解决方案，但这也需要更多的工作。 - Mark Byers