Задача . C. Казак Вус и строки

У Казака Вуса есть две бинарные строки, то есть строки, которые состоят только из «0» и «1». Назовем эти строки \(a\) и \(b\). Известно, что \(|b| \leq |a|\), то есть длина \(b\) не более \(a\).

Казак рассматривает каждую подстроку длины \(|b|\) строки \(a\). Назовем эту подстроку \(c\). Он сопоставляет соответствующие символы в \(b\) и \(c\), после чего считает количество позиций, где эти две строки различны. Назовем эту функцию \(f(b, c)\).

Например, пусть \(b = 00110\), а \(c = 11000\). В этих строках первая, вторая, третья и четвертая позиции различны.

Казак Вус считает количество таких подстрок \(c\), что \(f(b, c)\) — четное.

Например, пусть \(a = 01100010\), а \(b = 00110\). У \(a\) есть четыре подстроки длины \(|b|\): \(01100\), \(11000\), \(10001\), \(00010\).

• \(f(00110, 01100) = 2\);
• \(f(00110, 11000) = 4\);
• \(f(00110, 10001) = 4\);
• \(f(00110, 00010) = 1\).

Поскольку в трех подстроках \(f(b, c)\) четное, то ответ — \(3\).

Вус не умеет находить ответ для больших строк, поэтому просит вас помочь ему в этом.