R base packages only.

For regexpr with a sliding window I have

'''
bock_size = 10000
buffer = ""

repeat {
# concatenate  10000 numbers one at a time to the buffer
...
# if no match found shrink the buffer, and increment current number and position
}

We cannot use Rcpp - R base packages 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
  }
}

We cannot use Rcpp - R base packages 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
  }
}

R base packages only.

For regexpr with a sliding window I have

'''
bock_size = 10000
buffer = ""

repeat {
# concatenate  10000 numbers one at a time to the buffer
...
# if no match found shrink the buffer, and increment current number and position
}

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.

You can not use Rcpp, R base package only.

I have tried the KMP algorithm. It runs fine on small input, but poorly 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 programs are tested on hidden test cases. And even using the second approach, my program still timed out for 1 test case.

We cannot use Rcpp - R base packages only.