longest common substring in R finding non-contiguous matches between the two strings

by

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 R, and the stringdist package has a few functions that run the LCS method. Here’s a look at stringsidt. It returns the number of unpaired characters.

stringdist(a, b, method="lcs")
# [1] 7

Filter("!", mapply(
    stringdist, 
    stri_sub(b, 1, 1:nchar(b)),
    stri_sub(a, 1, 1:nchar(b)),
    MoreArgs = list(method = "lcs")
))
#  h  he hel 
#  0   0   0

Now that I’ve explored this a bit more, I think adist() might be the way to go. If we set counts=TRUE we get a sequence of Matches, Insertions, etc. So if you give that to stri_locate() we can use that matrix to get the matches from a to b. 

ta <- drop(attr(adist(a, b, counts=TRUE), "trafos")))
# [1] "MMMIIIMIIIIM"

So the M values denote straight across matches. We can go and get the substrings with stri_sub()

stri_sub(b, stri_locate_all_regex(ta, "M+")[[1]])
# [1] "hel" "l"   "o"

Sorry I haven’t explained that very well as I’m not well versed in string distance algorithms.

More Related Contents:

  1. Find common substrings between two character variables
  2. Grouping functions (tapply, by, aggregate) and the *apply family
  3. Create a sequential number (counter) for rows within each group of a dataframe [duplicate]
  4. Extracting specific columns from a data frame
  5. Can dplyr package be used for conditional mutating?
  6. Faster version of combn
  7. Subset a dataframe between 2 dates
  8. Assign multiple objects to .GlobalEnv from within a function
  9. What does .SD stand for in data.table in R
  10. How to move cells with a value row-wise to the left in a dataframe [duplicate]
  11. rep() with each equals a vector
  12. ggplot2 geom_bar – how to keep order of data.frame [duplicate]
  13. How to sum a numeric list elements
  14. Memory Allocation “Error: cannot allocate vector of size 75.1 Mb” [duplicate]
  15. How do I install an R package from the source tarball on windows?
  16. Merge 2 dataframes if value within range
  17. How do you create a progress bar when using the “foreach()” function in R?
  18. How to find the difference in value in every two consecutive rows in R?
  19. Replace duplicated elements with NA, instead of removing them
  20. RMarkdown: How to end tabbed content
  21. reading global variables using foreach in R
  22. Group by using base R
  23. rolling joins data.table in R
  24. Rstudio is duplicating commands in the command line
  25. list members can be accessed with partial name? Is this a feature?
  26. How do you create vectors with specific intervals in R?
  27. How do I draw gridlines using abline() that are behind the data?
  28. r random forest error – type of predictors in new data do not match
  29. R ggplot ordering bars within groups
  30. ggplot for loop outputs all the same graph

Leave a Comment