regex - 检查给定模式是否由正则表达式生成

Question

我有一个正则表达式和一个要匹配的模式字符串。我需要检查模式是否是由正则表达式生成的有效字符串。

现在问题变得有趣了，因为正则表达式只能包含 ' * ' 字符和一个预定义的字母 set(az) 。

这里'*'的含义：

if regex is "a*": its closure { '','a','aa','aaa',.. }
if its "ab*c" : its closure { 'ac','abc','abbc', ... }

现在，有一个回溯解决方案，检查所有可能性。

我想知道，既然如此，we only have " * " as a special symbol我们能否以更好的复杂性来做到这一点。

Answer 1

我们可以以更好的复杂性来做吗？

是的。只需省略回溯，您就没有需要它们的交替。只有你必须规范你的正则表达式：

1. 改变所有出现的X*XtoXX*
2. 改变所有出现的X*X*toX*

这可以以线性复杂度（相对于正则表达式的长度）来完成；那么您可以单次遍历输入字符串（输入长度​​具有线性复杂性）。