Необходимо создать кратчайшую строку, которая содержит в себе все строки из массива. Пример ниже.
Массив строк: 000, 001, 100, 011
Кратчайшая строка, которая содержит все предыдущие строки: 100011
Интересен сам алгоритм, нежели чем реализация.
Ответ
Эта задача относится к сложным как в реализации так и в скорости задачам.
Она может быть решена с помощью модернизированного алгоритма Ахо-Корасик http://e-maxx.ru/algo/aho_corasick . Конкретные детали реализации там же в предпоследнем абзаце (Нахождение кратчайшей строки, содержащей вхождения одновременно всех образцов) .
Важно! сложность будет порядка 2^n где n - количество строк.
Может искать эту задачу по запросу shortest common superstring она NP-полная.
Комментариев нет:
Отправить комментарий