1.什么是正则表达式
简单来说，就是使用一些特定的元字符来检索、匹配、替换符合规则的字符串。
2.正则表达式引擎
正则表达式就是一串符号，程序需要去分析它，并且建立一个语法树，然后根据这个树执行程序。这个程序就叫做状态机。
（1）DFA【确定有限状态自动机】【时间复杂度O(n)】
（2）NFA【非确定有限状态自动机】【时间复杂度O(ns)】
对比一下，DFA执行效率大于NFA。在编程语言里，都是使用NFA。
3.那么正则是如何匹配的？简单梳理一下
text = "aabcab";
regex = "bc"
拿正则第一个字符去匹配b---a失败，b----a，失败。
然后是b---b，这时候匹配上了。
下一步就是拿第二个字符c---c 刚好匹配上了。这时候就成功了。
4.以上是一个简单的理想化的匹配，NFA是如何回溯的呢？？
text = "abbc"
grex = "ab{1,3}c"
这个匹配的流程
首先正则第一个字符a---a ，匹配成功
第二个b---b，成功。但是这时候
第三个还是b，因为{1,3}，所有还是b---c.这时候就匹配失败
这时候就发生了回溯。第三个b---指定的还是b.而不是C。
5.避免回溯问题怎么办？
（1）独占模式
text=“abbc”
regex=“ab{1,3}+bc”
就是匹配不到就直接返回匹配结束。不存在回溯。
（2）懒惰模式【加个？号】
text=“abc”
regex=“ab{1,3}?c”
只匹配一个b.如果后续不成功，也不回溯。
（3）减少分支
例如，将“(abcd|abef)”替换为“ab(cd|ef)”
因为如果不替换，ab可能会匹配多次。提取出来，只需要匹配一次
网友评论