- Описание
- Отправленные решения
357. Граф подстрок
Антон стажируется в группе обработки комментариев и отзывов. Для проверки гипотезы об автоматической генерации текстов Антон должен построить граф подстрок существующих текстов.
Антон берёт все имеющиеся у него слова и действует следующим образом:
- слово $S=s_{1}s_{2} ... s_{n-1}s_{n}$ образует $n-2$ слова длины 3: $w_{1}=s_{1}s_{2}s_{3}$, $w_{2}=s_{2}s_{3}s_{4}$, $w_{3}=s_{3}s_{4}s_{5}$ $\ldots$ $w_{n-2}=s_{n-2}s_{n-1}s_{n}$;
- если для какого-то из слов $w_{i}$ еще нет вершины в графе, то она создается;
- для каждой пары слов $(w_{i},w_{i+1})$ добавляется ориентированное ребро веса 1, или увеличивается вес существующего ребра на 1.
Таким образом получается граф $G$ с $v$ вершинами и $e$ ориентированными рёбрами. Между некоторыми вершинами может быть несколько дуг (от $a$ к $b$ и от $b$ к $a$).
По заданному набору слов помогите Антону найти количество вершин в графе и вывести ориентированные рёбра между вершинами.
Формат ввода
В первой строке записано одно целое число $T$ ($1 \le T \le 40\,000$) — количество слов, имеющихся у Антона.
В каждой из $T$ следующих строк записано одно слово $S_i$ ($4 \le |S_i| \le 30$). Все слова состоят из строчных букв английского алфавита.
Формат вывода
В первой строке выведите количество вершин $v$ в графе $G$.
Во второй строке выведите количество пар вершин $e$, между которыми есть ориентированные ребра.
В каждой из следующих $e$ строк выведите слово $w_s$, соответствующее началу ребра, затем слово $w_f$, соответствующее концу ребра, и вес ориентированного ребра из вершины $w_s$ в $w_f$.
Рёбра вы можете перечислить в произвольном порядке.
Ограничения
Ограничение времени
6 с
Ограничение памяти
128 МБ
Пример 1
2
aaaaaaaaaaaaa
aaabbbaaabbba
6
7
aaa aaa 10
aaa aab 2
aab abb 2
abb bbb 2
bbb bba 2
bba baa 1
baa aaa 1
Пример 2
2
abab
baba
2
2
aba bab 1
bab aba 1
Пример 3
1
qwertyqwertyqwertyqwertyqwerty
6
6
qwe wer 5
wer ert 5
ert rty 5
rty tyq 4
tyq yqw 4
yqw qwe 4