12
$\begingroup$

I'm looking for a way to get the longest common substring for multiple strings such as

{home/dir1/dir2/jmoasd.txt,home/dir1/dir2/ivbnoxcihv.txt,home/dir1/dir2/siuhgiuchv.txt}

should yield

home/dir1/dir2/

Is there a different way to do this other than the character-by-character comparison until unmatched or LongestCommonSubsequence[] (which only takes 2 elements)?

Thanks!

$\endgroup$
2
  • $\begingroup$ For your example the common sequences are the initial sequences, which is quite a lot easier to handle than the general question. Is common initial sequences all you need? $\endgroup$
    – george2079
    Commented May 12, 2016 at 20:08
  • $\begingroup$ In general, there is no the longest common substring, because there can be several of them. For example, for "AABB" and "BBAA", both "AA" and "BB" are longest common substrings. This also explains why in case of $>2$ strings you cannot just fold over the list of strings, finding LCS between only 2 strings at each step. $\endgroup$ Commented May 13, 2016 at 21:46

1 Answer 1

11
$\begingroup$

You can first compare two of the strings, get the longest common string, and then take the result and compare it to the third string. And keeping do it until the last string in the list will give you the longest common string for all the strings. This can be achieved using Fold, for example:

ls = {"home/dir1/dir2/jmoasd.txt", "home/dir1/dir2/ivbnoxcihv.txt", 
   "home/dir1/dir2/siuhgiuchv.txt"};
Fold[LongestCommonSubsequence, First@ls, Rest@ls]
(* "home/dir1/dir2/" *)

Edit

As JasonB pointed out, this method may fail when the sequence is not line up from the beginning in each string. In that case, one can use the method by Dr. belisarius:

longest[ls_] := 
 FromCharacterCode[(ToCharacterCode /@ 
     ls) /. {{___, Longest[y__], ___}, {___, y__, ___} ...} -> {y}]

ls // longest
(* "home/dir1/dir2/" *)

It also works for cases like:

{"aaaxxbbb", "bbbxxccc", "cccxxaaa"} // longest
(* "xx" *)
$\endgroup$
9
  • 3
    $\begingroup$ But what if the longest common sequence overall isn't the longest sequence between any two individual elements? $\endgroup$
    – Jason B.
    Commented May 12, 2016 at 16:48
  • $\begingroup$ @JasonB I'm taking the result of the longest common string and comparing it to the next string. I think at the end, it should be the common longest string for all the elements. $\endgroup$ Commented May 12, 2016 at 16:59
  • 3
    $\begingroup$ I had this answer posted but deleted it. It works for OP's example, but it wouldn't work for {"aaaxxbbb", "bbbxxccc", "cccxxaaa"}. Because the longest common substring (LCS) of the three is not contained in the LCS of any pair. $\endgroup$
    – Jason B.
    Commented May 12, 2016 at 17:47
  • 2
    $\begingroup$ @JasonB wait!?! screaming kids doesn't enhance your ability to concentrate? :) $\endgroup$
    – rcollyer
    Commented May 12, 2016 at 20:14
  • 2
    $\begingroup$ @rcollyer Other people tell how they can work from home.... I go to the office for peace and quiet $\endgroup$
    – Jason B.
    Commented May 12, 2016 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.