Все общие подпоследовательности в массиве строк

Question

Я пытаюсь найти ВСЕ общие подпоследовательности в массиве строк в ruby, а не только в самой длинной подпоследовательности.

Это означает, что если вход

["aaaF привет", "aaaG привет", "aaaH привет"]

Ожидаемый результат

["ааа", "привет"]

Я возился с самым длинным алгоритмом одиночной подпоследовательности, но не могу понять, как получить соответствующий вывод. Проблема большинства подходов состоит в том, что в конечном массиве есть другие элементы, такие как "a", "aa", "h", "he", "hel", "hell"

Answer 1

Ну, эти меньшие подпоследовательности, такие как "а" и "аа", являются общими подпоследовательностями, так что это не будет неверным.

Если вы действительно хотите только самые длинные общие подпоследовательности (то есть те подпоследовательности, которые не содержатся ни в одной другой общей подпоследовательности), вам нужно проверить, являются ли эти подпоследовательности частью большей общей подпоследовательности, и, если это так, отбросить их.

Это может быть сделано с помощью (в псевдокоде)

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);
   }
}

Удачи!

Answer 2

1. выберите строку s из массива.
2. итерация по всем подстрокам s, которые на одну короче, чем s.
3. для каждой подстроки проверьте, существует ли она во всем массиве.
4. если это так, добавьте его к результату и продолжите., если это не так, перейдите к 1 с подстрокой как s.

Вот некоторый код в Python/ псевдо:

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