O(n)
O(ns)
text="aabcab" regex="bc"
text="abbc" regex="ab{1,3}c"
读取正则表达式第一个匹配符a和字符串第一个字符a进行比较,a对a,匹配
读取正则表达式第二个匹配符b{1,3}和字符串的第二个字符b进行比较,匹配,但b{1,3}表示1~3个字符,而NFA自动机具有 贪婪 特性,所以不会读取正则表达式的下一个匹配符c
使用b{1,3}和字符串的第四个字符c进行比较,发现不匹配,此时就会发生 回溯 ,已经读取的字符串第四个字符c将被吐出去,指针回到第三个字符b的位置
发生回溯后,读取正则表达式的下一个匹配符c,和字符串的第四个字符c进行比较,结果匹配
避免回溯的方法:使用 懒惰 模式和 独占 模式
+、?、*、{min,max}
等量词,正则表达式会匹配 尽可能多 的内容 text="abbc" , regex="ab{1,3}c"
,发生了一次匹配失败,就会引起一次回溯 text="abbbc" , regex="ab{1,3}c"
,匹配成功 ?
开启懒惰模式, text="abc" , regex="ab{1,3}?c"
"abc"
,在该模式下NFA自动机首先选择 最小 的匹配范围,即匹配1个b字符, 避免了回溯问题 +
开启懒惰模式, text="abbc" , regex="ab{1,3}+bc"
match("ab{1,3}c", "abbc"); // abbc,贪婪模式,产生回溯 match("ab{1,3}c", "abbbc"); // abbbc,贪婪模式,不产生回溯 match("ab{1,3}?", "abbbb"); // ab,懒惰模式,不产生回溯 match("ab{1,3}+bc", "abbc"); // null,独占模式,不产生回溯
"(X|Y|Z)"
的正则表达式会 降低性能 ,尽量减少使用,如果一定要使用
(abcd|abef)
=> ab(cd|ef)
(X|Y|Z)
()
就是一个捕获组
(?:exp)
组成 String text = "<input high=/"20/" weight=/"70/">test</input>"; String reg = "(<input.*?>)(.*?)(</input>)"; Pattern p = Pattern.compile(reg); Matcher m = p.matcher(text); while (m.find()) { System.out.println(m.group(0));// 整个匹配到的内容 System.out.println(m.group(1));//(<input.*?>) System.out.println(m.group(2));//(.*?) System.out.println(m.group(3));//(</input>) // 输出: // <input high="20" weight="70">test</input> // <input high="20" weight="70"> // test // </input> }
String text = "<input high=/"20/" weight=/"70/">test</input>"; String reg = "(?:<input.*?>)(.*?)(?:</input>)"; Pattern p = Pattern.compile(reg); Matcher m = p.matcher(text); while (m.find()) { System.out.println(m.group(0));// 整个匹配到的内容 System.out.println(m.group(1));//(.*?) // 输出 // <input high="20" weight="70">test</input> // test }
在做好性能测试的前提下,可以使用正则表达式,否则 能不用就不用 ,避免造成更多的性能问题