自己实现正则表达式

作者: | 更新日期:

比赛

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

作为一个合格的程序员,日常工作中使用正则表达式应该是常态。
那你有没有想过正则表达式是如何实现的呢?

刚好,leetcode 上有一个简化版的正则表达式题目,我们来看看吧。

一、题意

给一个正则表达式,由小写字母、*?组成。

*代表匹配任意字符串,包括空字符串。
?代表匹配任意一个字符。

问正则表达式是否匹配输入的纯小写字母字符串。

二、基本做法

我们不去管正则表达式,就按题目的要求去作者道题的话,会发现这是一个动态规划题。

比如从前到后看,可以定义函数f(l, r) 代表判断以l位置开始的字符串是否与以r位置开始的正则表达式。
其中入口是f(0, 0)

这里有很多状态转移和出口。

1、lr都结束,则匹配
2、l未结束,r结束,则不匹配
3、l结束,r未结束,则r后面全为*时匹配,否则不匹配。
4、如果lr相等或者r是为?,则判断f(l+1, r+1)
5、如果r不为*,则不匹配。
6、此时r*,如果r是最后一个字符,则匹配。
7、依次假设*的长度为L=0~MAX,检查f(l+L, r+1),只要一个匹配则算匹配。
8、否则当前函数不匹配。

复杂度:O(nm)
其中n是字符串的长度,m是正则的长度。
由于正则一般不会很长,这个算法还可以接受。

四、优化

可以发现,当正则匹配时,其实速度很快,马上结束了流程。
而不匹配的时候,需要回溯继续匹配,这导致最终复杂度是O(nm)

可以发现,正则里是字母或者?时,不需要回溯,只需要判断f(l+1,r+1)
而正则是*时,才是产生O(nm)的根本原因。

如果我们可以减少*的话,回溯次数就会减少。

比如连续的*按一个处理,这些都是初级的优化。

这里还有一个高级的优化,可以大大降低不匹配时的均摊复杂度。

比如对于输入串是S0 S1 S0 S1 S3,正则是* S1 * S2
最终结果是不匹配。

则匹配到第一个S1后,会判断f(S0 S1 S3, * S2),然后得出结果不匹配。
匹配到第二个S1后,会判断f(S3, * S2),最终得出的还是不匹配。

其实匹配第一个S1后结果是不匹配,则可以确定整个串不匹配了。
这样计算量直接减少一半,如果*多了,可以减少大量的务必要的判断。

那为什么可以确定后面肯定不匹配呢。
这里可以使用反证法。

假设第一个不匹配,第二个匹配,即第二个S1后,f(S3, * S2)匹配。

由于S0 S1 S3S3相比,只是多了一个前缀,这个前缀可以用* S2*来消除。
因此f(S0 S1 S3, * S2)也是匹配的。

假设不成立,所以之后肯定不会匹配。

由此,可以愉快的使用这个优化了。

代码如下。

五、最后

好了,初级的正则表达式就介绍到这里了。

这里主要分析了基本的动态规划方法,还介绍了多个*时的一个不错的剪枝策略。

剪枝策略你看懂了吗?
关于进一步优化,你是不是想到了KMP呢?
有什么思路吗?

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越