琥珀色呑んだくれ備忘録

メモとか備忘録とか

Rで最長共通部分文字列を取り出す

やりたかったこと

与えられた文字列に共通する部分文字列を取り出したい。PTXQCというパッケージにLCSn()というツールが容易されている。

CRAN - Package PTXQC

install.packages("PTXQC", dependencies = TRUE)
PTXQC::LCSn(c("AAAAACBBBBB", "AAAAADBBBBB", "AAAABBBBBEF")) 
> [1] "BBBBB"

問題の名前

最長共通部分文字列(Longest common substrings; LCS)、とよばれる古典的な問題らしい。最長共通部分列Longest common subsequence)と呼ばれるよく似た問題も同じLCSなので、メモしておかないと忘れる。

 

Longest common substrings

qiita.com

Longest common subsequence qiita.com