Орнамент на шырдаке
Мастерица из Кочкора разложила огромный шырдак — прямоугольник из N × M клеток, в каждой клетке свой цвет (строчная латинская буква). Заказчица принесла образец орнамента размером A × B и хочет найти на шырдаке все места, где этот орнамент встречается. Образец можно поворачивать на 90°, 180° и 270° (но не переворачивать зеркально).
Найдите количество прямоугольных участков шырдака, которые совпадают с образцом хотя бы в одном из четырёх поворотов. Участок задаётся положением и размерами; если он совпадает с образцом в нескольких поворотах, его считают один раз.
Входные данные
В первой строке — четыре целых числа N M A B (1 ≤ N, M ≤ 1000, 1 ≤ A, B ≤ 1000). Далее N строк по M букв — шырдак. Далее A строк по B букв — образец.
Выходные данные
Выведите количество подходящих участков.
Пример 1
Вход:
3 4 1 2
abac
bcab
aaab
ab
Выход:
6
Пояснение
Образец ab встречается без поворота в трёх местах, повёрнутым на 180° (ba) — в одном, повёрнутым на 90° или 270° (вертикально: a над b или b над a) — ещё в двух. Всего 6 участков.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов N, M ≤ 30.
Подсказка
Двумерный полиномиальный хеш позволяет сравнивать прямоугольники за O(1).
Комментарии