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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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 / 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