1934: Забагато букв, не читав
Перегляд у форматі PDFЄ ~n~ періодичних рядків з символів 'a', 'b', 'c', 'd', довжини не менше ~4~. Періодичний рядок - це будь-який підрядок (не тільки префікс) нескінченного рядка ~abcdabcdabcd...~ Підрядок - це набір послідовних сусідніх символів рядка у порядку зліва направо, можна уявити собі як символи даного рядка з ~l~-го по ~r~-й.
Для кожного з ~n~ рядків ми можемо обрати будь-який його підрядок (можливо, пустий) і об'єднати в будь-якому порядку так, щоб отримати префікс (тобто результат починається з 'a') рядка ~abcdabcdabcd....~ Назвемо це комбінацією рядків.
Потрібно порахувати найбільшу можливу довжину комбінації, що відповідає усім умовам.
Input
У першому рядку записано ціле число ~n~ - кількість рядків: ~(1 \le n \le 10^5)~
У наступних ~n~ рядках записано періодичні рядки (довжини не менше ніж ~4~) ~s_i~ ~(1 \le |s_i| \le 2*10^5)~
Гарантується, що сумарна довжина всіх періодичних рядків не перевищує ~10^6~ символів.
Output
У першому рядку виведіть ціле число ~ans~ — найбільшу можливу довжину комбінації, що відповідає усім умовам.
Sample Input 1
3
bcdabcd
abcd
abcdabc
Sample Output 1
16
- Виберемо з 'bcdabcd' підрядок 'dabcd'
- Виберемо з 'abcd' підрядок 'abcd'
- Виберемо з 'abcdabc' підрядок 'abcdabc'
- Об'єднаємо: 'abcdabc' + 'dabcd' + 'abcd' == 'abcdabcdabcdabcd'
Sample Input 2
2
abcd
bcdabcd
Sample Output 2
8
- Виберемо з 'abcd' підрядок 'abcd'
- Виберемо з 'bcdabcd' підрядок: 'abcd'
- Об'єднаємо 'abcd' + 'abcd' == 'abcdabcd' Зверніть увагу, не можна об'єднати 'bcdabcd' + 'abcd' == 'bcdabcdabcd', бо комбінація має починатись з 'a'.
Коментарі
Розбір від автора:
Побудуємо граф на 4х вершинах, де рядок це ребро з стану початку до стану який доповнює кінець (нехай 0, 1, 2, 3 - початок з , , і відповідно). При кожній колізії (якщо ми хочемо об'єднати рядки ~k1~ і ~k2~ саме в такому порядку) ми відкинемо спільні символи або з ~k1~ або з ~k2~, оскільки після об'єднання в обох випадках ми отримаємо однаковий результат - відкидатимемо префікс ~k2~. Додамо до нашого графу ребра ~\{3 \rightarrow 2, 2 \rightarrow 1, 1 \rightarrow 0, 0 \rightarrow 3\}~, які репрезентуватимуть видалення першого символу для рядка який ми візьмемо. Тоді, якщо ми оптимально додали ребра (додали мінімальну допустиму кількість) - то в графі існуватиме Ейлерів шлях, який репрезентуватиме процес побудови рядка. Додамо ці ребра так, щоб задовольнити умови Ейлерового шляху (~indeg~=~outdeg~, крім старту і фінішу + зв'язність графу), також потрібно буде перебрати фініш і перевірити підвипадок, коли можливо зробити Ейлерів цикл. Фіктивний старт завжди буде в ~3~ (), щоб побудова почалась з . Відповідь: ~\sum{|s_i|} - \#доданих\ ребер~.