Нахождение наименьшего количества подстрок для представления набора строк

Question

Я хотел бы найти набор непересекающихся подстрок, которые можно объединить для представления заданного набора строк. Предположим, что данный набор строк

abc0def
zabc1def
abc2defg

тогда наименьший набор непересекающихся подстрок, которые могут быть объединены для формирования полного набора строк выше, равен

abc
def
0
1
2
g
z

Чтобы уточнить: под неперекрывающимися я подразумеваю, что ни один член набора не начинается и не заканчивается одинаковой последовательностью символов.

Answer 1

Используйте строки для построения ориентированного графа с символами в виде вершин и дуг, указывающих от символов к следующим символам.Для любой вершины с степенью двух или более удалите все входящие дуги.Аналогично, для тех, у кого степень выше двух или более, удалите все исходящие дуги.После удаления оставшиеся компоненты графа являются путевыми графами, представляющими подстроки;просто следуйте по пути, чтобы построить подстроки.

Вам также нужно будет ввести фиктивные вершины для начала и конца строк.Это позволяет избежать проблем, например, с abcde и bcd.