像这样的正则表达式(对任何字符串进行操作)的时间复杂度是多少:"(.{5})11"
我的实现是:
reps <- function(s, n) paste(rep(s, n), collapse = "") # repeat s n times
find.string <- function(string, th = 3, len = floor(nchar(string)/th)) {
for(k in len:1) {
pat <- paste0("(.{", k, "})", reps("\1", th-1))
r <- regexpr(pat, string, perl = TRUE)
if (attr(r, "capture.length") > 0) break
}
if (r > 0) substring(string, r, r + attr(r, "capture.length")-1) else ""
}
请务必帮忙。谢谢!:)
这取决于实现。由于反向引用,这在严格的单词定义中不是正则表达式,但它看起来像是最坏情况O(15 * length(string))
解释:正则表达式引擎将尝试从位置0,1,2,3,4开始匹配。字符串中的最后一个位置。由于没有约束(点字符),它将匹配任何前5个字符,然后将尝试再次匹配它们两次,最坏的情况是进行15次查询,然后失败。然后它将移动到字符串中的第二个位置,并尝试再次执行此操作。所以,在最坏的情况下它会执行len(string)几次