Мы порождаем все триплеты используя алфавит из 26 английских букв (A = {a, b, c, ..., z}):
A3 = A × A × A =
{
(a, a, a),
(a, a, b),
(a, a, c),
...,
(a, a, z),
(b, a, a),
...,
(z, z, y),
(z, z, z),
}
|A3| = 263 = 17576
Если мы попытаемся слить триплеты aaa и bbb, то нам придётся прикрепить bbb к концу строки aaa, так как они не перекрываются:
merge(aaa, bbb) = aaabbbНо если мы сливаем строку aaa со строкой aab, то мы получим результат меньшей длины:
merge(aaa, aab) = aaab
В лучшем случае, если нам получится всегда делать слияния второго типа, то для каждого триплета (кроме первого) мы будем просто удлинять результирующую строку на 1 символ. Всего у нас есть 17576 триплетов, так что мы добавим к результирующей строке 17575 символов. В результате этих добавлений финальная строка, содержащая все возможные триплеты, будет иметь длину 17575 + 3 = 17578.
В худшем случае мы всегда будем делать операцию слияния первого типа, что приведёт к результирующей строке длины 17576 * 3 = 52728.
Лучший результат находится где-то в интервале [17578, 52728].
Как же нам скомбинировать все триплеты, чтобы получить строку минимальной длины?
Картинка для привлечения внимания.