Let X = "1234567891011..." the infinite string contains all positive integers. *str* is a sequence of digits. We are asked to find the first location in X that *str* appears. I have tried the KMP algorithm. It runs fine on small input, make did poor on input such as *str* = "667788999". It takes forever to finish. I also tried to use regexpr with a sliding window, the above test case will still cost 20s. Our program are tested on unknown test cases. And even using the second approach, my program still timedout for 1 test case. Are there any ways to improve the efficiency, or any other algorithms? You can not use Rcpp, R base package only. ``` KMP_version = function(s) { pattern = as.integer(strsplit(s, "")[[1]]) m = length(pattern) compute_failure = function(pattern) { n = length(pattern) lps = integer(n) len = 0 lps[1] = 0 for (i in 2:n) { while (len > 0 && pattern[len + 1] != pattern[i]) { len = lps[len] } if (pattern[len + 1] == pattern[i]) { len = len + 1 } lps[i] = len } return(lps) } get_digits = function(num) { if (num == 0) return(0) digits = integer(floor(log10(num)) + 1) idx = length(digits) while (num > 0) { digits[idx] = num %% 10 num = num %/% 10 idx = idx - 1 } return(digits) } lps = compute_failure(pattern) idx = 0 # current matching idx in s pos = 0 # current pos in S, the infinite string n = 1 # current number repeat { digits = get_digits(n) for (digit in digits) { pos = pos + 1 while (idx > 0 && digit != pattern[idx + 1]) { idx = lps[idx] } if (digit == pattern[idx + 1]) idx = idx + 1 if (idx == m) return(pos - m + 1) } n = n + 1 } } ``` ``` regexpr_version = function(s) { m = nchar(s) buffer = "" # Buffer to hold the sliding window pos = 0 # Position in the infinite string S n = 1 # Current number to append batch_size = 10000 repeat { numbers = paste0(n:(n + batch_size - 1), collapse = "") search_str = paste0(buffer, numbers) match = regexpr(s, search_str, fixed = TRUE)[1] # match found if (match != -1) { start_pos = pos - nchar(buffer) + match return(start_pos) } pos = pos + nchar(numbers) buffer = substr(search_str, nchar(search_str) - m + 2, nchar(search_str)) n = n + batch_size } } ```