我访问了多个网站，只是为了了解字符串类中使用的任何正则表达式函数(如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);
我想了解的是，如果正则表达式内部对O(n(进行运算，其中n是字符串的长度，那么我的代码(使用正则表达式(在时间复杂性方面类似于一般的在线代码(使用for循环(。
提前谢谢。
Regex太复杂了，无法进行如此简单的分析。
有一种东西叫做Thompson/NFA正则表达式解析器。这样的正则表达式解析器具有O(n+m(性能，其中n是正则表达式的长度，m是输入字符串的长度。然而，TNFA无法处理反向引用、各种查找/反向，并且存在其他问题。一旦您开始在regexp中使用这些"TNFA取消资格"功能，实际上就不可能从regexp引擎中挤出o(n+m(性能。这方面的证据相当微不足道。此正则表达式：
/^1?$|^(11+?)1+$/
将匹配长度为素数且仅由"1"个符号组成的输入字符串。它会使其他事情失败。
这个工作(检查素数(不能在O(n(中完成。因此，任何能够运行上述正则表达式的正则表达式解析器都不能是O(n+m(，QED。
现在，一个相关的问题是：如果输入regexp只使用基本功能，比如regexp可以由Thompson/NFA风格的状态机处理，那么java会使用它吗？
答案似乎与你的问题无关，因为你在这里使用回溯法。然而，如果内存可用，java就不会附带TNFA实现，并且将始终使用回溯器。然而，这并没有写入规范中，因此一些未来版本可以根据输入regexp中使用的功能智能地切换元素。目前(截至JDK14(的实现完全支持java.util.regexp.Pattern类的javadoc中所解释的整个功能集(其中包括TNFA引擎无法完成的功能，如回溯(，这确实意味着java的正则表达式引擎中的某些正则表达式比Thompson/NFA引擎需要更长的数量级。
更多关于Thompson/NFA的信息。
re2j是Thompson/NFA的java实现。如果您希望在java中使用有保证的线性性能(O(n+m)(正则表达式，请使用此选项。从数学上讲，re2j不支持反向引用和其他一些东西(请参阅网站上的列表(，因此它无法运行(.)\1{1,}表达式——这是因为从数学上来说，在O(n)时间内不可能做到这一点。