Ctrl K

Слова-рамки

Сложная
Дан список слов words. Скажем, что слово a **обрамляет** слово b, если b одновременно начинается и заканчивается на a. Например, «aba» обрамляет «ababa», а «abc» не обрамляет «abcd». Любое слово обрамляет само себя. Посчитайте пары индексов (i, j) с i < j, для которых words[i] обрамляет words[j].
Пример 1
words=['ab', 'abab', 'b', 'ab'] → 2

«ab» — и начало, и конец «abab» (пара (0, 1)); вторая «ab» совпадает с первой целиком (пара (0, 3)). «b» не начинает ни одно слово после себя.

Пример 2
words=['xyx', 'x', 'xyxyx'] → 2

«xyx» и «x» обрамляют «xyxyx» с обеих сторон. Пара (0, 1) не годится: более длинное слово стоит раньше.

Ограничения
  • 1 ≤ len(words) ≤ 10⁵
  • 1 ≤ len(words[i]) ≤ 10⁵
  • Суммарная длина всех слов не больше 5·10⁵
  • Слова состоят из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСлова-обложки ЛёгкаяЦель из начал слов СредняяФраза из начал слов: длинная версия СложнаяПалиндром дописыванием слева СложнаяФрагменты-повторы Сложная
загружаем Python…
Вход
words=['ab', 'abab', 'b', 'ab']
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 71 тест на сервере, включая скрытые.