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