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

Question

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

abc0def 
zabc1def 
abc2defg 

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

abc 
def 
0 
1 
2 
g 
z 

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

Answer 1

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

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