PHP 正则表达式效率贪婪、非贪婪与回溯分析(推荐)

2024-10-03 02:41:08

先扫盲一下什么是正则表达式的贪婪，什么是非贪婪？或者说什么是匹配优先量词，什么是忽略优先量词？

好吧，我也不知道概念是什么，来举个例子吧。

某同学想过滤之间的内容，那是这么写正则以及程序的。

$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪

看起来，好像没什么问题，其实则不然。若

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';

那么经过上面的程序处理，其结果为

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script>alert(document.cookie)</script>

仍然达不到他想要的效果。上面的就是非贪婪，也有的叫惰性。其标志非贪婪的标识为量数元字符后面加? ，比如 +?、*?、??(比较特殊，以后的BLOG中，我会写到)等。即标识非贪婪，如果不写?就是贪婪。比如

$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script 只有这些了，好像还是不太合适，哈，您知道如何重写那个正则吗？

以上为贪婪，非贪婪的区别介绍。下面，聊下贪婪、非贪婪引起的回溯问题。先看个小例子。

正则表达式为\w*(\d+)，字符串为cfc456n，那么，这个正则匹配的$1是多少？？

如果您回答是 456,那么，恭喜你，回答错了，其结果不是456，而是6，您知道为什么吗？

CFC4N来解释一下，当正则引擎用正则\w*(\d+)去匹配字符串cfc456n时，会先用\w*去匹配字符串cfc456n，首先，\w*会匹配字符串cfc456n的所有字符，然后再交给\d+去匹配剩下的字符串，而剩下的没了，这时，\w*规则会不情愿的吐出一个字符，给\d+去匹配，同时，在吐出字符之前，记录一个点，这个点，就是用于回溯的点，然后\d+去匹配n，发现并不能匹配成功，会再次要求\w*再吐出一个字符，\w*会先再次记录一个回溯的点，再吐出一个字符。这时，\w* 匹配的结果只有cfc45了，已经吐出6n了，\d+再去匹配6，发现匹配成功，则会通知引擎，匹配成功了，就直接显示出来了。所以，(\d+)的结果是6，而不是456。

当上面的正则表达式改为 \w*?(\d+)（注意，此处为非贪婪），字符串仍然为cfc456n，那么，这时候，正则匹配的$1是多少？？

甲同学回答：结果是 456。

嗯，是的，正确，是456，CFC4N弱弱的问下，为什么是456 呢？

我在来解释一下为什么是456

正则表达式有条规则，是量词优先匹配，所以\w*?会先去匹配字符串cfc456，由于\w*?是非贪婪，正则引擎会用表达式\w+?每次仅匹配一个字符串,然后再将控制权交给后面的\d+去匹配下一个字符，同时，记录一个点，用于在匹配不成功的时候，返回这里，再次匹配，也就是回溯点。由于\w后面是量词是*，*表示0到无数次，所以，首先是0次，也就是\w*?匹配个空，记录回溯点，将控制权交给\d+,\d+去匹配cfc456n的第一个字符c,然后，匹配失败，于是乎，接着讲控制权交给\w*?去匹配cfc456n的c，\w*?匹配c成功，由于是非贪婪，所以，他每次只匹配一个字符，记录回溯点，然后再将控制权交给\d+匹配f,接着，\d+匹配f再失败，再把控制权给\w*?，\w*?再匹配c,记录回溯点（这时\w*?匹配结果是cfc了），再把控制权给\d+，\d+去匹配4，匹配成功，然后，由于量词是+，就是1到无数次，所以，接着往后匹配，再匹配5，成功，再接着，再匹配6，成功，再接着，继续匹配操作，下一个字符是n，匹配失败，这时，\d+会吧控制权交出去。由于\d+后面已经没有正则表达式了，所以，整个正则表达式宣告匹配完成，其结果就是 cfc456, 其中第一组结果是456。亲爱的同学，您明白刚刚的题目的结果，为什么是456了吗？

好了，您是否从上面的例子了解了贪婪，非贪婪的匹配原理了？那您是否明白您在什么时候需要使用贪婪，非贪婪去处理您的字符串了？

鸟哥的文章里讲到针对表达式、程序为

$reg = "/<script>.*?<\/script>/is";
$str = "<script>********</script>"; //长度大于100014
$ret = preg_repalce($reg, "", $str); //返回NULL

其原因就是回溯太多了，直到造成耗尽栈空间爆栈。

再来看个例子。

字符串

$str = '<script>123456</script>';

正则表达式为

$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';

以上所述是小编给大家介绍的PHP 正则表达式效率贪婪、非贪婪与回溯分析，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

php约瑟夫问题解决关于处死犯人的算法

本文实例讲述了php约瑟夫问题解决关于处死犯人的算法.分享给大家供大家参考.具体分析如下: 古代某法官要判决IV个犯人的死刑,他有一条荒唐的法律将犯人站成一个圆圈,从第s个人开始数起,每到第D个人就拉出来处死,然后再数D个,再拉出来处决-- 直到剩下最后一个可以赦免. function getNum($n,$m){ //用于把所有的数存到数组初始化 $a = array(); //遍历,存入数组 for($i=1;$i<=$n;$i++){ $a[$i] = $i; } //指针归0 reset
PHP贪婪算法解决0-1背包问题实例分析

本文实例讲述了PHP贪婪算法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活! //0-1背包贪心算法问题 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } }
PHP使用栈解决约瑟夫环问题算法示例

本文实例讲述了PHP使用栈解决约瑟夫环问题算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php cla
php实现猴子选大王问题算法实例

本文实例讲述了php实现猴子选大王问题算法.分享给大家供大家参考.具体分析如下: 一.问题: n只猴子围坐成一个圈,按顺时针方向从1到n编号. 然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数, 如此重复,直至剩下一个猴子,它就是大王. 设计并编写程序,实现如下功能: (1) 要求由用户输入开始时的猴子数$n.报数的最后一个数$m. (2) 给出当选猴王的初始编号. 二.解决方法: /** * @param int $n 开始时的猴子数
PHP实现的回溯算法示例

本文实例讲述了PHP实现的回溯算法.分享给大家供大家参考,具体如下: 问题: 一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少头中牛,多少头小牛? 实现代码: <?php /* * k = 2x + y + 1/2z 取值范围 * 0 <= x <= 1/2k * 0 <= y <= k * 0 <= z < = 2k * x,y,z最大值 2k */ $daMi = 100; $result = array();
PHP回溯法解决0-1背包问题实例分析

本文实例讲述了PHP回溯法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 这段代码是根据<软件设计师>教程的伪代码写的: 最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题: 带着调试输出一块写上 <?php $v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bkna
PHP实现基于回溯法求解迷宫问题的方法详解

本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.
PHP基于回溯算法解决n皇后问题的方法示例

本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向
PHP正则表达式的效率回溯与固化分组

先来看下问题. 字符串复制代码代码如下: $str = '<script>123456</script>'; 正则表达式为复制代码代码如下: $strRegex1 = '%<script>.+<\/script>%'; $strRegex2 = '%<script>.+?<\/script>%'; $strRegex3 = '%<script>(?:(?!<\/script>).)+<\/scri
Python正则表达式教程之三：贪婪/非贪婪特性

之前已经简单介绍了Python正则表达式的基础与捕获,那么在这一篇文章里,我将总结一下正则表达式的贪婪/非贪婪特性. 贪婪默认情况下,正则表达式将进行贪婪匹配.所谓"贪婪",其实就是在多种长度的匹配字符串中,选择较长的那一个.例如,如下正则表达式本意是选出人物所说的话,但是却由于"贪婪"特性,出现了匹配不当: >>> sentence = """You said "why?" and I say
PHP 正则表达式效率贪婪、非贪婪与回溯分析(推荐)

先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧. 某同学想过滤之间的内容,那是这么写正则以及程序的. $str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪看起来,好像没什么问题,其实则不然.若 $str = '<script<script>alert(document.cookie)</script&
php正则表达式中的非贪婪模式匹配

一般情况下,正则表达式的匹配是贪婪模式的,比如下面这个例子: 字符串:....src="http://www.bloghome.cn/1.mp3" type="application/x-mplayer2" .... 要求的结果:http://www.bloghome.cn/1.mp3 如果匹配表达式写为:/src="(.*)"/,则得不到正确的结果,因为最后一个双引号的匹配是贪婪模式的. 解决办法:匹配表达式写为: /src="(.*
浅谈php正则表达式中的非贪婪模式匹配的使用

通常我们会这么写: 复制代码代码如下: $str = "http://www.baidu/.com?url=www.sina.com/"; preg_match("/http:(.*)com/", $str, $matches); print_r($matches); 结果: 复制代码代码如下: Array ( [0] => http://www.baidu/.com?url=www.sina.com [1] => //www.baidu/.com?
正则表达式之贪婪与非贪婪模式详解（概述）

1 概述贪婪与非贪婪模式影响的是被量词修饰的子表达式的匹配行为,贪婪模式在整个表达式匹配成功的前提下,尽可能多的匹配,而非贪婪模式在整个表达式匹配成功的前提下,尽可能少的匹配.非贪婪模式只被部分NFA引擎所支持. 属于贪婪模式的量词,也叫做匹配优先量词,包括: "{m,n}"."{m,}"."?"."*"和"+". 在一些使用NFA引擎的语言中,在匹配优先量词后加上"?",即变成属于非
小议正则表达式效率贪婪、非贪婪与回溯

先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧. 某同学想过滤之间的内容,那是这么写正则以及程序的. 复制代码代码如下: $str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪看起来,好像没什么问题,其实则不然.若复制代码代码如下: $str = '<script<script>alert(docume
php正则表达式中贪婪与非贪婪介绍

一.贪婪与非贪婪什么叫贪婪,比如说要从字符串中<td>面包一</td><td>面包二</td>吃面包,本来你只可以吃面包一,可是你贪心,于是就把第一个<td>到最后一个</td>里面的两个面包取出来了,你想多吃点,非贪婪也就是你不贪吃了,就只吃面包一. 我们来看看正则里面是怎么贪婪的 <?php $str = '<td>面包一</td><td>面包二</td>'; preg_ma
[正则表达式]贪婪模式与非贪婪模式

复制代码代码如下: /** ** author: site120 ** function : get script part from html document **/ var loadJs = function(str , delayTime) { var delayTime = delayTime || 100; var regExp_scriptTag = new RegExp("<\\s*sc
Python正则表达式非贪婪、多行匹配功能示例

本文实例讲述了Python正则表达式非贪婪.多行匹配功能.分享给大家供大家参考,具体如下: 一些regular的tips: 1 非贪婪flag >>> re.findall(r"a(\d+?)","a23b") # 非贪婪模式 ['2'] >>> re.findall(r"a(\d+)","a23b") ['23'] 注意比较这种情况: >>> re.findall(r&q
python中如何使用正则表达式的非贪婪模式示例

前言本文主要给大家介绍了关于python使用正则表达式的非贪婪模式的相关内容,分享出来供大家参考学习,下面话不多说了,来一起详细的介绍吧. 在正则表达式里,什么是正则表达式的贪婪与非贪婪匹配如:String str="abcaxc"; Patter p="ab*c"; 贪婪匹配:正则表达式一般趋向于最大长度匹配,也就是所谓的贪婪匹配.如上面使用模式p匹配字符串str,结果就是匹配到:abcaxc(ab*c). 非贪婪匹配:就是匹配到结果就好,就少的匹配字符.如上

PHP 正则表达式效率 贪婪、非贪婪与回溯分析(推荐)

相关推荐

随机推荐

PHP 正则表达式效率贪婪、非贪婪与回溯分析(推荐)