Орнамент на шырдаке


Отправить решение Решать в редакторе

Сложность: 80%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Мастерица из Кочкора разложила огромный шырдак — прямоугольник из 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).


Комментарии

Еще нет ни одного комментария.