检查一个正则表达式是否包含另一个正则表达式

Question

我正在尝试实现文本聚类算法.该算法通过用正则表达式替换它们来聚类相似的原始文本行,并聚合与每个正则表达式匹配的模式的数量,以便提供输入文本的简洁摘要,而不是显示来自输入文本的重复模式.在这次尝试中,我遇到了寻找一个正则表达式是否覆盖另一个正则表达式的需要.

假设我们关注仅约与"*"和"+"外卡,即"*"意味着一个字母的零个或多个字符的字符串,而"+"代表一个字母的1点或多个正好正则表达式.还假设字符集为ASCII.

例如:

1. AB covers AB
      This is straightforward.
2. ABC* covers ABC
      Because ABC* can generate: ABC, ABCC, ABCCC etc.
3. A*B+C* covers AB+C*
      Because A*B+C* can generate ABBC, AABBC, AABBCC etc. which covers
      all strings generated by AB+C*.
4. A+M+BC* covers AMM+B+C+M+BC*
      Similar to case [3] above.

基本上我正在寻找以下方法的有效实现,该方法告诉strA(可能包含正则表达式)是否覆盖了strB(可能包含正则表达式).请注意,还应该有一种方法可以在输入字符串strA和strB中转义正则表达式字符'*'和'+'.

C++中的方法签名:

bool isParentRegex(const string& strA, const string& strB)

我的想法是实现需要一个递归方法,它可能有点复杂.但我很想知道我是否可以重用现有的实现而不是重新发明轮子,或者是否有任何其他直接的方法来实现它.

Answer 1

请检查此 Perl 模块源代码，但请记住它不适用于所有正则表达式（因为它将导致解决停止问题。