R grepl：快速将多个字符串与多个子字符串匹配，返回所有匹配项

我在 R 中有相当大的字符串集：

set.seed(42)
strings <- sapply(1:250000, function(x) sample(2:20, 1, prob=c(
  0.001, 0.006, 0.021, 0.043, 0.075, 0.101, 0.127, 
  0.138, 0.132, 0.111, 0.087, 0.064, 0.042, 0.025, 0.014, 0.008, 
  0.004, 0.002, 0.001)))
strings <- lapply(strings, function(x) sample(letters, x, replace=TRUE))
strings <- sapply(strings, paste, collapse='')

我想创建一个列表，表示这些字符串中的子字符串列表中每个元素是否存在。当然，我的出发点是来自 stackoverflow 的一些代码 https://stackoverflow.com/questions/9537797/r-grep-match-one-string-against-multiple-patterns:

#0.1 seconds
substrings <- sample(strings, 10)
system.time(matches <- lapply(substrings, grepl, strings, fixed=TRUE)) 

然而，这种方法对于较大的子字符串集来说有点幼稚，因为它存储所有匹配项和所有非匹配项：

#13 seconds
substrings <- sample(strings, 1000)
system.time(matches <- lapply(substrings, grepl, strings, fixed=TRUE)) 

我们可以通过仅存储匹配来减少输出对象的大小：

#13 seconds
substrings <- sample(strings, 1000)
system.time(matches <- lapply(substrings, function(x) which(grepl(x, strings, fixed=TRUE))))

但对于大量子字符串来说，这仍然很慢：

#316 seconds
substrings <- sample(strings, 25000)
system.time(matches <- lapply(substrings, function(x) which(grepl(x, strings, fixed=TRUE))))

时间呈线性增长很好，但我觉得必须有一种更快的方法来完成这项任务，也许可以避免lapply loop.

如何加速这个多对多字符串匹配功能？

/edit：一种简单的加速方法是并行化：

#Takes about 99 seconds
require('doParallel')
cl <- makeForkCluster(nnodes=8)
registerDoParallel(cl)
system.time(matches <- foreach(i=1:length(substrings)) %dopar% {
  which(grepl(substrings[i], strings, fixed=TRUE))
})
stopCluster(cl)

然而，我认为一旦找到快速串行算法，这个问题的大多数解决方案将很容易并行化。