longest common substring problem

Question

Does anyone know of an R package that solves the longest common substring problem? I am looking for something fast that could work on vectors.

Answer 1

Check out the "Rlibstree" package on omegahat: http://www.omegahat.org/Rlibstree/.

This uses http://www.icir.org/christian/libstree/.

Answer 2

I don't know R, but I used to implement Hirschberg's algorithm which is fast and don't consume too much space.

As I remember it is only 2 or 3 recursively called short functions.

Here is a link: http://wordaligned.org/articles/longest-common-subsequence

So don't hesitate to implement it in R, it worths the effort since it is a very interesting algorithm.