| Codeforces Round 336 (Div. 2) |
|---|
| Закончено |
Геносу нужна Ваша помощь. Сайтама попросил его решить следующую задачку по программированию:
Обозначим как |s| длину некоторой строки s. Расстояние Хэмминга между двумя строками s и t одинаковой длины определяется как 
, где si означает i-й символ строки s, а ti — i-й символ строки t. Например, расстояние Хэмминга между строкой "0011" и строкой "0110" равно |0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2.
Даны две строки a и b, найдите сумму расстояний Хэмминга между a и всеми подстроками b длины |a|.
В первой строке входных данных записана двоичная строка a (1 ≤ |a| ≤ 200 000).
Во второй строке входных данных записана двоичная строка b (|a| ≤ |b| ≤ 200 000).
Гарантируется, что обе строки состоят только из символов '0' и '1'.
Выведите единственное целое число — сумму расстояний Хэмминга между a и всеми подстроками строки b длины |a|.
01
00111
3
0011
0110
2
В первом примере в строке b есть четыре подстроки длины |a|: "00", "01", "11", и "11". Расстояние между "01" и "00" равно |0 - 0| + |1 - 0| = 1. Расстояние между "01" и "01" равно |0 - 0| + |1 - 1| = 0. Расстояние между "01" и "11" равно |0 - 1| + |1 - 1| = 1. Последнее значение учитывается два раза, поскольку подстрока "11" встречается в b дважды. Сумма этих расстояний равна 1 + 0 + 1 + 1 = 3.
Второй пример описан в условии задачи.
