2024-09-27 19:32:12 发布
网友
import re for _ in range(int(input())): s=input() #input alphanumeric string print(sum(map(int,re.findall('\d+',s))))
此模式的findall的时间复杂度应为O(len(s)) 正则表达式不是回溯的,所以它应该可以在线性时间内进行匹配。 然而,我不知道re的实现,但如果它在线性时间上不匹配,我会感到惊讶
这应在线性时间O(n)内运行。检查与正则表达式的时间复杂性相关的问题
What is the complexity of regular expression?
What's the Time Complexity of Average Regex algorithms?
时间复杂度很难说,因为大多数正则表达式都是在正则语言上形成的。现在所有的正则语言都有其有限自动机,它可以用DFA、NFA或e-NFA来表示。一个正则表达式需要多长时间不仅取决于要匹配的模式的大小,还取决于计算该正则表达式的有限自动机。它也可能取决于实际发动机。如果它直接构造DFA,那么每次在输入字符串上匹配时,其长度上限为(O(n))
此模式的findall的时间复杂度应为O(len(s)) 正则表达式不是回溯的,所以它应该可以在线性时间内进行匹配。 然而,我不知道re的实现,但如果它在线性时间上不匹配,我会感到惊讶
这应在线性时间O(n)内运行。检查与正则表达式的时间复杂性相关的问题
What is the complexity of regular expression?
What's the Time Complexity of Average Regex algorithms?
时间复杂度很难说,因为大多数正则表达式都是在正则语言上形成的。现在所有的正则语言都有其有限自动机,它可以用DFA、NFA或e-NFA来表示。一个正则表达式需要多长时间不仅取决于要匹配的模式的大小,还取决于计算该正则表达式的有限自动机。它也可能取决于实际发动机。如果它直接构造DFA,那么每次在输入字符串上匹配时,其长度上限为(O(n))
相关问题 更多 >
编程相关推荐