Найти общие подстроки между двумя символьными переменными

У меня есть две символьные переменные (имена объектов), и я хочу извлечь самую большую общую подстроку.

a <- c('blahABCfoo', 'blahDEFfoo')
b <- c('XXABC-123', 'XXDEF-123')

В результате я хочу следующее:

[1] "ABC" "DEF"

Эти векторы в качестве входных данных должны давать одинаковый результат:

a <- c('textABCxx', 'textDEFxx')
b <- c('zzABCblah', 'zzDEFblah')

Эти примеры являются репрезентативными. Строки содержат идентифицирующие элементы, а остальная часть текста в каждом векторном элементе является общей, но неизвестной.

Есть ли решение в одном из следующих мест (в порядке предпочтения):

База R
Рекомендуемые пакеты
Пакеты, доступные в CRAN

Ответ на предполагаемый дубликат не отвечает этим требованиям.

Ответ 1

Вот пакет CRAN для этого:

library(qualV)

sapply(seq_along(a), function(i)
    paste(LCS(strsplit(a[i], '')[[1]], strsplit(b[i], '')[[1]])$LCS,
          collapse = ""))

Ответ 2

Если вы не возражаете против использования пакетов bioconductor, тогда вы можете использовать Rlibstree. Установка довольно проста.

source("http://bioconductor.org/biocLite.R")
biocLite("Rlibstree")

Затем вы можете сделать:

require(Rlibstree)
ll <- list(a,b)
lapply(data.frame(do.call(rbind, ll), stringsAsFactors=FALSE), 
           function(x) getLongestCommonSubstring(x))

# $X1
# [1] "ABC"

# $X2
# [1] "DEF"

На стороне примечания: я не совсем уверен, что Rlibstree использует libstree 0.42 или libstree 0.43. Обе библиотеки присутствуют в исходном пакете. Я помню, как я столкнулся с утечкой памяти (и, следовательно, ошибкой) в огромном массиве в perl, который использовал libstree 0.42. Просто голова.

Ответ 3

Поскольку у меня слишком много вещей, которые я не хочу делать, я сделал это вместо этого:

Rgames> for(jj in 1:100) {
+ str2<-sample(letters,100,rep=TRUE)
+ str1<-sample(letters,100,rep=TRUE)
+ longs[jj]<-length(lcstring(str1,str2)[[1]])
+ }
Rgames> table(longs)
longs
 2  3  4 
59 39  2

Кто-нибудь хочет сделать статистическую оценку фактического распределения совпадающих строк? (lcstring - это просто перетаскиваемая функция грубой силы, выход содержит все максимальные строки, поэтому я смотрю только на первый элемент списка)