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$
  • $\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 May 12 '16 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$ – Vladimir Reshetnikov May 13 '16 at 21:46
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" *)
| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ But what if the longest common sequence overall isn't the longest sequence between any two individual elements? $\endgroup$ – Jason B. May 12 '16 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$ – xslittlegrass May 12 '16 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. May 12 '16 at 17:47
  • 2
    $\begingroup$ @JasonB wait!?! screaming kids doesn't enhance your ability to concentrate? :) $\endgroup$ – rcollyer May 12 '16 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. May 12 '16 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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