All Common Subsequences in Array of Strings

Question

I'm trying to find ALL common subsequences in an array of strings in ruby not just the longest single subsequence.

This means that if the input is

["aaaF hello", "aaaG hello", "aaaH hello"]

The expected output is

["aaa", " hello"]

I've been messing with the longest single subsequence algorithm, but can't figure out how to get the appropriate output. The problem with most approaches is they have other elements in the final array like "a", "aa", "h", "he", "hel", "hell"

i dont understand why "aaa" and "hello" are valid results while "aa" for example isnt — yurib, Nov 16 '11 at 08:08

score 1 · Accepted Answer · answered Nov 16 '11 at 08:24

1

Well, these smaller subsequences like "a" and "aa" are common subsequences, so that wouldn't be incorrect.

If you really only want the longest common subsequences (i.e. those subsequences not contained in any other common subsequence), what you need to do is to check whether these subsequences are part of the larger common subsequence, and if so, discard them.

This can be done by (in pseudocode)

finalsubsequences = copy(subsequences);
for(subseq in subsequences) {
   for(subseq2 in subsequences) {
       if(subseq2.indexOf(subseq) != false)
       // subseq contains subseq2, thus discard subseq2
       finalsubsequences.remove(subseq2);
   }
}

Good luck!

answered Nov 16 '11 at 08:24

Willem Mulder

12,974
3
37
62

I've tried to implement this but couldn't get it to work correctly. Any chance you could draw up actual code? – user1026817 Nov 16 '11 at 08:36
Not in Ruby unfortunately, but in javascript or php, sure, if you like. – Willem Mulder Nov 16 '11 at 08:39
I've already done it in PHP, I'm new to ruby so that's why it's tripping me up, thanks though – user1026817 Nov 16 '11 at 08:44
Figured out the issue, when iterating through the array, use .dup – user1026817 Nov 16 '11 at 09:10
Great that you figured it out. Good luck with other remaining work :) – Willem Mulder Nov 16 '11 at 09:14

yurib · Answer 2 · 2011-11-16T08:23:20.633

0

choose a string s from the array.
iteratate over all substrings of s that are shorter by one then s.
for each substring check to see if it exists in the entire array.
if it is, add it to the result and continue., if it is not, go to 1 with the substring as s.

heres some code in python/pseudo:

A = String["aaaf hello","aaag hello"]

def find(s):
   res = []
   for sub in [s[1:],s[:-1]]
     if sub in all items in A:
       res.append(sub)
     else:
       res.append(find(sub))
   return res

edited Nov 16 '11 at 08:23

answered Nov 16 '11 at 08:18

yurib

8,043
3
30
55

Hmm, let me work on an implementation of your suggestion in Ruby. – user1026817 Nov 16 '11 at 08:28
you know what, i tried it and its not exactly right... i think willem's suggestion is better... sorry. – yurib Nov 16 '11 at 08:35

All Common Subsequences in Array of Strings

2 Answers2