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