我正在尝试编写一个正则表达式来验证字符串。它应该验证要求,即它应该仅包含大写和小写英文字母(a 到 z、A 到 Z)(ASCII:65 到 90、97 到 122)和/或数字 0 到 9(ASCII:48 到57) AND 字符 - _ ~ (ASCII: 45, 95, 126)。前提是它们不是第一个或最后一个字符。它也可以有性格。 (点、句点、句号)(ASCII:46) 前提是它不是第一个或最后一个字符,并且也不是连续出现两次或多次。我尝试过使用以下内容
Pattern.compile("^[^\\W_*]+((\\.?[\\w\\~-]+)*\\.?[^\\W_*])*$");
它适用于较小的字符串,但不适用于长字符串,因为我遇到了线程挂起问题和 CPU 的巨大峰值。请帮忙。
无效字符串的测试用例:
"aB78."
"aB78..ab"
"aB78,1"
"aB78 abc"
".Abc12"
有效字符串的测试用例:
"abc-def"
"a1b2c~3"
"012_345"
最佳答案
您的正则表达式患有catastrophic backtracking ,这导致求解时间为 O(2n)(即指数)。
虽然点击链接将提供更全面的解释,但简单来说,问题是当输入不匹配时,引擎会回溯第一个*
项尝试不同的术语数量组合,但由于所有组或多或少都匹配相同的事物,因此分组方式的组合数量随着回溯的长度呈指数增长 - 在不匹配输入的情况下,回溯的长度是整个输入。
解决方案是重写正则表达式,这样它就不会灾难性地回溯:
- 不要使用组的组
- 使用所有格量词,例如
.*+
(永不回溯) - 因不匹配而提前失败(例如使用锚定的负面前瞻)
- 使用
{n,m}
样式量词限制术语可能出现的次数
或者以其他方式缓解问题
关于Java 正则表达式卡在一条长绳上,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27901615/