552. Тандемная конкатенация

Не решаласьСредняя

Тандем - это строка четной длины, у которой левая и правая половины равны.

Дан набор из nn строк (1n1051 \le n \le 10^5). Найдите среди них такие пары, которые при конкатенации дают тандем. Более формально, найдите все пары (ii, jj) такие, что iji \ne j и строка sis_i+sjs_j является тандемом.

Выведите все упорядоченные пары индексов (нумерация с единицы).

Формат ввода

В первой строке дано целое число nn (1n1000001 \le n \le 100\,000) - количество строк.

Далее в nn строках записано по одному слову. Длина каждого слова от 11 до 1010. Слова состоят из маленьких букв английского алфавита.

Формат вывода

Выведите все упорядоченные пары индексов (нумерация с единицы).

Примечание

Генерация тестов (кроме примеров из условия)

Для генерации тестов использовался следующий алгоритм:

  1. выбираются два числа nn (1n1110001 \le n \le 111\,000) и kk (2k262 \le k \le 26)
  2. выбираются kk различных символа английского алфавита
  3. генерируются nn строк: сначала выбирается длина \ell от 11 до 1010 с равномерным распределением, затем генерируется строка из выбранных символов и длины \ell
  4. оставляем только уникальные строки (если их более 100000100\,000, то 100000100\,000 случайных)

Ограничения

Ограничение времени

6 с

Ограничение памяти

256 МБ

Пример 1

Ввод
4
a
abbaa
bba
abb
Вывод
2 3
3 2

Пример 2

Ввод
4
tan
dem
tandemtan
demtandem
Вывод
1 4
2 3
3 2
4 1

Пример 3

Ввод
4
a
aa
aaa
aaaa
Вывод
1 3
2 4
3 1
4 2

Теги

Нужно войти, чтобы отправить решение.Войти