ДНК реп'яховірусу
Обмеження: 2 сек., 256 МіБ
ДНК (і реп’яховірусу, і людини, і будь-якої іншої істоти) можна представити у вигляді рядка, що складається з маленьких літер латинської абетки.
У результаті довготривалих експериментів Зеник та Марічка побудували теорію впливу реп’яховірусу на людину.
Коефіцієнтом подібності двох послідовностей ДНК однакової довжини називається сума індексів (починаючи з одиниці), у яких ці послідовності збігаються.
Коефіцієнтом впливу вірусу з ДНК \(s\) на людину з ДНК \(t\) називається сума коефіцієнтів подібності між \(s\) та всіма підрядками \(t\) такої ж довжини, як \(s\).
Напишіть програму для знаходження коефіцієнту впливу вірусу на людину.
Вхідні дані
У першому рядку задано \(t\).
У другому рядку задано \(s\).
Вихідні дані
В одному рядку виведіть ціле число — коефіцієнт впливу вірусу з ДНК \(s\) на людину з ДНК \(t\).
Обмеження
\(1 \le |t|, |s| \le 10^5\), де \(|x|\) — це довжина рядка \(x\),
\(s\) і \(t\) складаються з малих літер латинської абетки.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| abacaba ab | 7 |
Примітки
Підрядки \(t\) довжини 2:
ab, ba, ac, ca,
ab, ba.
Їхні коефіцієнти подібності з \(s\): 3, 0, 1, 0, 3, 0.
\(3+0+1+0+3+0=7\).
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
ДНК реп’яховiрусу - Розбір
Яка довжина найкоротшого шляху, що починається в корені дерева проходить через усі листки дерева, а тоді повертається у корінь? Легко бачити, що такий шлях проходить по кожному ребру рівно 2 рази, а тому його довжина — \(2n - 2\), де \(n\) — кількість вершин у дереві.
Як змінюється ця довжина якщо нам не потрібно повертатися в корінь після відвідування останнього листка? Нехай \(D_v\) — відстань від кореня до вершини \(v\) (ми також називатимемо цю величину глибиною вершини \(v\)). Зрозуміло, що закінчивши у листку \(x\), ми економимо рівно \(D_x\) ребер. Отже, вигідно закінчити наш маршрут у вершині, для якої \(D_v\) максимальне.
Таким чином, щоб відповісти на запит другого типу нам потрібно знати кількість вершин у піддереві, а також глибину найглибшого листка. Якби не було запитів першого типу, то було б достатньо обчислити ці значення для усіх вершин за допомогою пошуку в глибину. Як же бути з запитами першого типу? Від задачі з додаванням вершин перейдемо до задачі з "увімкненням" вершин. Розглянемо дерево, що вийде після виконання усіх запитів першого типу (ми називатимемо його фінальним деревом). Тепер вважатимемо, що кожна вершина в цьому дереві може бути або увімкненою, або ні. Коли відбувається запит першого типу, то ми вмикаємо відповідну вершину. Для запиту другого типу нам потрібно знайти кількість увімкнених вершин у піддереві та максимальну глибину серед увімкнених вершин у піддереві.
Побудуємо Ейлеровий обхід фінального дерева: випишемо усі вершини дерева в порядку обходу в глибину. Кожному піддереву відповідає деякий неперервний відрізок в цьому обході. Це дозволяє перетворити запити на піддереві у запити на відрізку. Отож, тепер нам потрібна структура даних, що ефективно виконує такі операції:
змінити значення елемента (щоб увімкнути вершину)
знайти суму на відрізку (щоб знайти кількість вершин у піддереві)
знайти максимальний елемент на відрізку (щоб знайти найглибшого листка)
Одна з таких структур — дерево відрізків. Вона може виконувати кожен з цих запитів з логарифмічною складністю.
Загальна складність — \(O(n + q \log(n))\).
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|