regex - Time complexity of regular expression with backreferencing -

what time complexity of regular expression (to operated on string): "(.{5})\1\1"

the implementation having is:

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 "" } 

please out. thanks! :)

it depends on implementation. not regular expression in strict definition of word because of backreferences, looks worst case o(15 * length(string))

explanation: regex engine try match starting position 0,1,2,3,4..last position in string. since there no constraint (dot character) match first 5 characters , try match them again twice, worst case doing 15 queries , failing. move 2nd position in string , try on again. so, in worst case len(string) times.