Областная олимпиада по информатике 2019 год


Задача E. Меж двух миров

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Алан живет в мире под номером $A$. Нурдаулет живет в мире под номером $B$. В мире $A$, если одна строка является префиксом другой, то они считаются одинаковыми. У Нурдаулета есть $n$ строк, он хочет узнать количество неупорядоченных пар $i, j$ таких, что Алану они покажется одинаковыми. Помогите Нурдаулету с задачей. Обозначим $|s|$ как длину строки $s$. Строка $s$ является префиксом строки $t$, если $|s| <= |t|$ и строка $s$ равна строке, образованной из первых $|s|$ символов строки $t$.
Формат входного файла
В первой строке дается единственное число $n (1 <= n <= 100000)$ — количество строк. В следующих $n$ строках дается по одной строке $s_i$. Гарантируется, что суммарная длина строк не превышает $500000$.
Формат выходного файла
Выведите единственное число — ответ на задачу.
Система оценки
В 40 процентах тестов $n <= 100$. В 20 процентах тестов, длины всех строк равны.
Пример:
Вход
3
ab
abc
ab
Ответ
3
( Alan Amanov )
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 2   0
2019-07-09 06:59:14.0 #

показать/скрыть код