例如，在下面给出的代码中，正则表达式方法的时间复杂度是多少：

Question

import re

for _ in range(int(input())):

s=input()                                      #input alphanumeric string 

print(sum(map(int,re.findall('\d+',s))))

Answer 1

此模式的findall的时间复杂度应为O（len（s）） 正则表达式不是回溯的，所以它应该可以在线性时间内进行匹配。 然而，我不知道re的实现，但如果它在线性时间上不匹配，我会感到惊讶