我访问过多个网站，只是为了了解string类中使用的任何regex函数（如split（）和replaceall（））的内部工作方式。
问题陈述可在以下位置获得：https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/one-string-no-trouble-37037871/
我的代码：
String s = "abaaccasdraaaadsfd";
s = s.replaceAll("(.)\\1{1,}", "$17$1");
String[] s2 = s.split("7");
int len = 0;
for(String a : s2) {
if(a.length() > len) {
len = a.length();
}
}
System.out.println(len);在线通用代码：
String s = "abaaccasdraaaadsfd";
int count=0;
int max=0;
for(int i=1;i<str.length();i++){
char ch =str.charAt(i-1);
char ch1=str.charAt(i);
if(ch!=ch1){
count++;
if(max<count){
max=count;
}
}else{
count=0;
}
}
System.out.println(max+1);我想了解，如果regex在内部操作o（n），其中n是字符串的长度，那么我的代码（使用regex）在时间复杂度方面与一般的在线代码（使用for循环）类似。
提前谢谢。
1条答案
按热度按时间nhn9ugyo1#
正则表达式对于如此简单的分析来说太复杂了。
有一个叫做thompson/nfa regexp解析器的东西。这样的regexp解析器具有o（n+m）性能，其中n是regexp的长度，m是输入字符串的长度。但是，tnfas不能处理backreference、各种lookahead/lookbacks，并且存在其他问题。一旦开始在regexp中使用这些“tnfa取消资格”特性，实际上就不可能从regexp引擎中挤出o（n+m）性能。这方面的证据相当微不足道。此regexp:
/^1?$|^(11+?)\1+$/将匹配长度为素数且仅由“1”符号组成的输入字符串。它会使其他事情失败。这个作业（检查素数）不能在o（n）中完成。因此，任何可以运行上述regexp的regexp解析器都不能是o（n+m），qed。
现在，一个相关的问题是：如果输入regexp只使用基本特性，这样regexp就可以由一个thompson/nfa风格的状态机来处理，那么java是否使用这个特性，而不是使用一个简单的回溯实现？
答案似乎与你的问题无关，因为你在这里使用回溯。但是，如果内存可用，java就不会附带tnfa实现，而是始终使用backtracker。然而，这并没有写入规范中，因此一些未来的版本可以根据输入regexp中使用的特性智能地切换IMElements。当前（从jdk14开始）的实现完全支持java.util.regexp.pattern类的javadoc中解释的整个特性集（其中包括tnfa引擎无法完成的特性，例如回溯），这确实意味着java的regex引擎比thompson/nfa引擎中的某些regex要花费更多数量级的时间。
更多关于汤普森/nfa的信息。
re2j是thompson/nfa的java实现。如果您想要保证线性性能，请使用此选项(
O(n+m))java中的正则表达式。正如数学上所指出的，re2j不支持反向引用和其他一些东西（请参阅站点中的列表），因此它无法运行(.)\\1{1,}表达式-这是因为从数学上讲，在O(n)时间。