Here is an excellent article on finding all common substrings efficiently, with examples in C. This may be overkill if you need just the longest, but it may be easier to understand than the general articles about suffix trees.
The Myers algorithm is a “divide and conquer algorithm”: it works by finding recursively the central match of two sequences with the smallest edit script. Once this is done only the match is memorized, and the two subsequences preceding and following it are compared again recursively until there is nothing more to compare. Finding the … Read more
Here’s a CRAN package for that: library(qualV) sapply(seq_along(a), function(i) paste(LCS(strsplit(a[i], ”)[[1]], strsplit(b[i], ”)[[1]])$LCS, collapse = “”))
Here are three possible solutions. library(stringi) library(stringdist) a <- “hello” b <- “hel123l5678o” ## get all forward substrings of ‘b’ sb <- stri_sub(b, 1, 1:nchar(b)) ## extract them from ‘a’ if they exist sstr <- na.omit(stri_extract_all_coll(a, sb, simplify=TRUE)) ## match the longest one sstr[which.max(nchar(sstr))] # [1] “hel” There are also adist() and agrep() in base … Read more