基于R实现高效的成对起始最长公共子串矩阵求解

核心逻辑 #

咱们要找的是从头开始连续匹配的最长公共子串，不是中间任意位置的公共子串，所以完全不用复杂的通用子串匹配算法，针对性优化就能大幅提速。

关于转二进制数的思路：短字符串凑合用，但长字符串（比如示例里的16位没问题，要是32位以上）转整数会溢出——R里整数最大是2^31-1，超了就变浮点数，精度直接丢失，反而导致匹配错误。所以这个方案局限性太大，不如直接操作字符串靠谱。

高效实现代码 #

基础版（适合中等规模字符串）

利用对称矩阵的特性，只计算上三角再复制到下三角，减少一半计算量：

mySolution <- function(x) {
  n <- length(x)
  # 初始化结果矩阵
  res_mat <- matrix("", nrow = n, ncol = n)
  
  # 自定义函数：计算两个字符串的起始最长匹配长度
  get_match_len <- function(s1, s2) {
    min_len <- min(nchar(s1), nchar(s2))
    # 从最长前缀往下找，找到第一个匹配的就返回
    for (len in min_len:1) {
      if (substr(s1, 1, len) == substr(s2, 1, len)) {
        return(len)
      }
    }
    return(0)
  }
  
  # 只计算上三角区域，对称复制到下三角
  for (i in 1:(n-1)) {
    for (j in (i+1):n) {
      match_len <- get_match_len(x[i], x[j])
      match_str <- substr(x[i], 1, match_len)
      res_mat[i, j] <- match_str
      res_mat[j, i] <- match_str
    }
  }
  res_mat
}

进阶优化版（适合大规模字符串）

如果字符串数量上千，预先生成所有前缀再批量比较，减少重复计算：

mySolution_fast <- function(x) {
  n <- length(x)
  res_mat <- matrix("", nrow = n, ncol = n)
  
  # 预先生成每个字符串的所有前缀列表
  prefixes <- lapply(x, function(s) {
    s_len <- nchar(s)
    if (s_len == 0) return("")
    sapply(1:s_len, function(k) substr(s, 1, k))
  })
  
  # 遍历两两组合，找最长公共前缀
  for (i in 1:n) {
    for (j in i:n) {
      if (i == j) next
      # 取两个前缀列表的交集，挑最长的那个
      common <- intersect(prefixes[[i]], prefixes[[j]])
      if (length(common) == 0) {
        match_str <- ""
      } else {
        match_str <- common[which.max(nchar(common))]
      }
      res_mat[i, j] <- match_str
      res_mat[j, i] <- match_str
    }
  }
  res_mat
}

测试验证 #

用题目给的输入测试：

x <- c("0100100010101010", "0100110010101010","0111001000","010111")
mySolution(x)

输出和示例完全一致：

[,1]     [,2]      [,3]      [,4]
[1,] ""       "01001"   "01"     "010"
[2,] "01001"  ""        "01"     "010"
[3,] "01"     "01"      ""       "01"
[4,] "010"    "010"     "01"     ""

关于二进制转整数的可行性 #

不推荐，原因有两个：

1. 长度限制：二进制字符串超过31位时，R的整数类型会溢出，转成浮点数后精度丢失，导致前缀匹配错误。
2. 额外开销：转二进制数本身需要计算，反而不如直接操作字符串高效，尤其是短字符串场景。

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