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, 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.
Are there any ways to improve the efficiency, or any other algorithms?
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
}
}
1 Answer 1
Instead of jumping straight into string searching, perhaps a complete change of approach is warranted?
I think we should start by examining the search string to see whether it's a sequence of consecutive 1-, 2-, ... n-digit numbers (remember to handle offsetting so that the first and last numbers may be incomplete - and if there's no repeat, we'll need to choose the lexicographically-lowest rotation of the digits). Once we have done that, it's a simple matter of arithmetic to calculate its position in the infinite list.
I recommend writing a set of unit tests to exercise the code. They won't be exactly the same as the hidden test battery, but with a sufficiently devious mind you can work outward from the simplest case to most complex, building up the function as you go.