ДНК реп'яховірусу
Обмеження: 2 сек., 256 МіБ
ДНК (і реп’яховірусу, і людини, і будь-якої іншої істоти) можна представити у вигляді рядка, що складається з маленьких літер латинської абетки.
У результаті довготривалих експериментів Зеник та Марічка побудували теорію впливу реп’яховірусу на людину.
Коефіцієнтом подібності двох послідовностей ДНК однакової довжини називається сума індексів (починаючи з одиниці), у яких ці послідовності збігаються.
Коефіцієнтом впливу вірусу з ДНК ss на людину з ДНК tt називається сума коефіцієнтів подібності між ss та всіма підрядками tt такої ж довжини, як ss.
Напишіть програму для знаходження коефіцієнту впливу вірусу на людину.
Вхідні дані
У першому рядку задано tt.
У другому рядку задано ss.
Вихідні дані
В одному рядку виведіть ціле число — коефіцієнт впливу вірусу з ДНК ss на людину з ДНК tt.
Обмеження
1≤|t|,|s|≤1051≤|t|,|s|≤105, де |x||x| — це довжина рядка xx,
ss і tt складаються з малих літер латинської абетки.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| abacaba ab | 7 |
Примітки
Підрядки tt довжини 2:
ab, ba, ac, ca,
ab, ba.
Їхні коефіцієнти подібності з ss: 3, 0, 1, 0, 3, 0.
3+0+1+0+3+0=73+0+1+0+3+0=7.