确定一个共同的模式

Question

是否有（容易）识别两个字符串共享的共同模式的可能性？这里有一个小例子来阐明我的意思：

我有两个包含字符串的变量。两者都包含相同的模式 ("ABC") 和一些 "noise"。

a <- "xxxxxxxxxxxABCxxxxxxxxxxxx"
b <- "yyyyyyyyyyyyyyyyyyyyyyyABC"

假设我不知道常见的模式，我希望 R 找出两个字符串都包含 "ABC"。我怎样才能做到这一点？

*编辑

第一个示例可能有点过于简单化。这是我真实数据的一个例子。

a <- "DUISBURG-HAMBORNS"
b <- "DUISBURG (-31.7.29)S"

两个字符串都包含 "DUISBURG"，我希望函数能够识别它。

*编辑

我采纳了评论中link提出的解决方案。但是我还是没有得到我想要的。

library(qualV)
LCS(strsplit(a[1], '')[[1]],strsplit(b[1], '')[[1]])$LCS

[1] "D" "U" "I" "S" "B" "U" "R" "G" "-" " " " " "S"

如果函数是寻找两个向量的最长公共子序列，为什么在"D" "U" "I" "S" "B" "U" "R" "G"之后还不停？ .

Answer 1

函数 LCS 来自 qualV 包（在 Find common substrings between two character variables; not a possible duplicate) does something else than what you need. It solves the longest common subsequence problem 中，其中子序列不需要占据原始序列中的连续位置。

您拥有的是 the longest common substring problem, for which you could use this 算法，这里是假设存在唯一（长度）最长公共子串的代码：

a <- "WWDUISBURG-HAMBORNS"
b <- "QQQQQQDUISBURG (-31.7.29)S"

A <- strsplit(a, "")[[1]]
B <- strsplit(b, "")[[1]]

L <- matrix(0, length(A), length(B))
ones <- which(outer(A, B, "=="), arr.ind = TRUE)
ones <- ones[order(ones[, 1]), ]
for(i in 1:nrow(ones)) {
  v <- ones[i, , drop = FALSE]
  L[v] <- ifelse(any(v == 1), 1, L[v - 1] + 1)
}
paste0(A[(-max(L) + 1):0 + which(L == max(L), arr.ind = TRUE)[1]], collapse = "")
# [1] "DUISBURG"

确定一个共同的模式

Identify a common pattern

string

r

lcs