Задача о наименьшей общей надстроке это задача поиска минимальной строки, которая содержит все данные в качестве подстрок Это наиболее естественная NP-полная задача, работающая со строками. Хотя задача о наименьшей общей надстроке выглядит проще, чем другие перестановочные задачи (например, она не сложнее, чем задача коммивояжера), однако до сих пор не существует алгоритмов обгоняющих тривиальный, получаемый динамическим программированием. В докладе будет рассказано, как использовать графы де Брюйна и похожие на них структуры, для того, что бы получить существенный выигрыш в скорости, для частного, но все еще NP-трудного случая коротких строк.