Побудуємо граф на 4х вершинах, де рядок це ребро з стану початку до стану який доповнює кінець (нехай 0, 1, 2, 3 - початок з 'a', 'b', 'c' і 'd' відповідно). При кожній колізії (якщо ми хочемо об'єднати рядки ~k1~ і ~k2~ саме в такому порядку) ми відкинемо спільні символи або з ~k1~ або з ~k2~, оскільки після об'єднання в обох випадках ми отримаємо однаковий результат - відкидатимемо префікс ~k2~. Додамо до нашого графу ребра ~\{3 \rightarrow 2, 2 \rightarrow 1, 1 \rightarrow 0, 0 \rightarrow 3\}~, які репрезентуватимуть видалення першого символу для рядка який ми візьмемо. Тоді, якщо ми оптимально додали ребра (додали мінімальну допустиму кількість) - то в графі існуватиме Ейлерів шлях, який репрезентуватиме процес побудови рядка. Додамо ці ребра так, щоб задовольнити умови Ейлерового шляху (~indeg~=~outdeg~, крім старту і фінішу + зв'язність графу), також потрібно буде перебрати фініш і перевірити підвипадок, коли можливо зробити Ейлерів цикл. Фіктивний старт завжди буде в ~3~ ('d'), щоб побудова почалась з 'a'. Відповідь: ~\sum{|s_i|}~ - доданих ребер.