Строки - 4
(Время: 1 сек. Память: 16 Мб Сложность: 48%)
Определим расстояние между равными по длине строками SA и SB (обозначим d(SA, SB)) как сумму для всех 1 ≤ i ≤ |SA| кратчайших расстояний между буквами SA(i) и SB(i) в циклически замкнутом английском алфавите (т.е. после буквы «a» идет буква «b», ..., после буквы «z» идет «a»). Например d(aba, aca) = 1, а d(aba, zbz) = 2.
Напомним, что циклическим сдвигом строки S называется строка (обозначим, как S→k) Sk+1Sk+2Sk+3 ... S|S|S1S2 ... Sk для некоторого k, где |S| – длина строки S.
Степенью циклического расстояния между строками SA и SB (|SA| = |SB|) называется сумма:
Требуется посчитать степень циклического расстояния заданных строк SA и SB.
Входные данные
Входной файл INPUT.TXT содержит две строки равной длины, не превышающей 105 символов. Строки состоят только из маленьких букв английского алфавита.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | a
b | 1 |
| 2 | ab
ac | 8 |
Пояснение
Во втором примере все циклические сдвиги строки «ab»: «ab» и «ba», все циклические сдвиги строки «ac»: «ac» и «ca». Искомое значение равно:
d(ab, ac) + d(ab, ca) + d(ba, ac) + d(ba, ca) = 1 + 3 + 3 + 1 = 8
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
