Как слить все строковые триплеты?
Difference between ru1 and ru2, changed 2 character(s)
Мы порождаем все триплеты используя алфавит из 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]$.↵

**Как же нам скомбинировать все триплеты, чтобы получить строку минимальной длины?**

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian egor.okhterov 2016-12-03 18:40:02 135 Мелкая правка: '*\n\n---\n![ ](htt' -
en4 English egor.okhterov 2016-12-03 18:36:17 117 Tiny change: ' length?**' -
en3 English egor.okhterov 2016-12-03 17:47:10 6 Tiny change: '-grams of smaller case le' -> '-grams of lower case le'
ru2 Russian egor.okhterov 2016-12-03 17:10:40 2 (опубликовано)
ru1 Russian egor.okhterov 2016-12-03 17:08:48 1380 Первая редакция перевода на Русский (сохранено в черновиках)
en2 English egor.okhterov 2016-12-03 15:28:51 948 Tiny change: 'e letters:\n$A_3 = $' - (published)
en1 English egor.okhterov 2016-12-03 15:05:57 182 Initial revision (saved to drafts)