Там сводится к скалярным произведениям, а как их находить, можно почитать на емаксе.

Лично у меня недавно (не больше месяца назад) зашло на тимусе (точнее упихнулось, возможно тесты слабые). Здесь тоже заходит за 998 миллисекунд.

Идея с FFT такова: нам даны два массива битов: a₀, ..., a_m - 1 и b₀, ..., b_n - 1, n ≤ m. Надо уметь находить для всех "разрешённых" k на отрезке [0, m - n] и выбрать среди них минимум. Пусть с_i = a_m - i при . Тогда

А второе выражение уже почти представляет из себя коэффициент какого-то произведения многочленов при m - k. Только XOR вместо произведения. Это легко исправить: Пусть C_i = ( - 1)^c_i, B_i = ( - 1)^b_i. Тогда если c_i = b_j, то C_i·B_j = 1, иначе C_i·B_j =  - 1. Пусть F — многочлен с коэффициентами C_i при xⁱ, G — многочлен с коэффициентами B_i при xⁱ. Тогда можно посчитать FG за с помощью FFT. Тогда заметим, что если коэффициент FG при x^m - k равен t, то .