如何在R中加速用于字符串有序子序列判断的for循环

问题本质 #

你需要判断的是kind字符串是否是word的子序列，即字符顺序一致、不需要连续。你当前的暴力双指针方案在数据量级达到1e5时超时，核心原因是每个待匹配字符串都需要完整遍历一次word，时间复杂度过高。

优化方案 #

我们采用「预构建字符索引+二分查找」的方案优化，仅需遍历一次word构建索引，后续每个待匹配字符串的匹配过程仅需做若干次二分查找，时间复杂度从O(待匹配数量 * word长度)降到O(word长度 + 所有待匹配字符串总长度 * log(word长度))，适配1e5量级的数据要求。

具体实现代码 #

input <- c("coronavirus", "4", "abcde", "crnas", "onarous", "ravus")
word <- input[1]
total <- as.numeric(input[2])
kind <- input[-c(1,2)]

# 预构建word的字符位置索引，仅需执行一次
word_chars <- unlist(strsplit(word, ""))
char_pos <- list()
for (i in seq_along(word_chars)) {
  c <- word_chars[i]
  if (is.null(char_pos[[c]])) {
    char_pos[[c]] <- integer(0)
  }
  char_pos[[c]] <- c(char_pos[[c]], i)
}
word_len <- length(word_chars)

# 匹配函数
check_subseq <- function(x) {
  x_len <- nchar(x)
  # 提前剪枝：长度超过word直接不匹配
  if (x_len > word_len) {
    return("NEGATIVE")
  }
  x_chars <- unlist(strsplit(x, ""))
  current_pos <- 0
  for (c in x_chars) {
    # 字符不存在直接返回不匹配
    if (is.null(char_pos[[c]])) {
      return("NEGATIVE")
    }
    pos_list <- char_pos[[c]]
    # 二分查找大于current_pos的最小位置
    idx <- findInterval(current_pos, pos_list) + 1
    if (idx > length(pos_list)) {
      return("NEGATIVE")
    }
    current_pos <- pos_list[idx]
  }
  return("POSITIVE")
}

# 批量执行并输出
result <- vapply(kind, check_subseq, FUN.VALUE = character(1))
cat(paste(result, collapse = "\n"), "\n")

额外说明 #

• 你原有代码存在bug：循环仅遍历到length(e)-1，word的最后一个字符不会参与匹配，会导致部分正确结果误判为NEGATIVE，优化后的代码已经修复该问题。
• 可以进一步把字符串拆分的操作向量化，减少循环中的重复计算，在待匹配字符串数量极大时能进一步提升速度。

内容的提问来源于stack exchange，提问作者Chennai Cheetah