Задача g6_1038: Система защиты (XIV Всероссийская олимпиада по информатике)

"ПермьОлимпБанк" разработал сверхнадежную систему защиты ценных бумаг. В правом верхнем углу любой бумаги должно присутствовать прямоугольное изображение в виде черно-белого рисунка. Для определения подлинности документов была создана библиотека контрольных элементов. Если документ подлинный, то в изображении на документе заданное количество раз присутствует каждый контрольный элемент из библиотеки. В библиотеке нет совпадающих элементов.
Система контроля после сканирования получает изображение в виде цифрового массива N M (N <= 100000, M <= 1000), в котором цифра 1 соответствует черному цвету, а цифра 0 - белому. Затем система ищет контрольные элементы в полученном массиве.
Контрольный элемент представляется массивом размером L*L (L <= 50) цифр, каждая из которых равна 0 или 1. В библиотеке - K контрольных элементов (K 20). Элемент библиотеки должен точно совпадать с какой-либо частью изображения. При сравнении изображения и контрольных элементов повороты не допускаются.
Требуется для каждого входного файла сформировать соответствующий ему выходной файл, в котором записано, сколько раз каждый элемент библиотеки встречается в изображении, описанном во входном файле.

Входные данные
В каталоге С:\TESTS\6 находятся 13 входных файлов с именами CONTROL.01, CONTROL.02, ..., CONTROL.13.
В первой строке каждого из этих входных файлов записаны через пробел числа N, M, K, L.
Далее следуют по порядку К блоков, соответствующих элементам контрольного образца в библиотеке. Каждый блок состоит из L строк по L цифр (ноль или единица). После каждого блока следует пустая строка.
В последующих N строках записаны по M цифр в каждой, соответствующих изображению.

Выходные данные
Вам требуется сдать 13 выходных файлов с именами:
P"номер участника"_6."номер теста"
где "номер участника" - пятизначный номер участника, 6 - номер задачи, "номер теста" - двузначный номер теста задачи.
Например, у участника с номером 21111 выходной файл для теста из файла CONTROL.03 должен называться P21111_6.03
Каждый выходной файл должен содержать К строк.
В каждой строке содержится два числа: номер контрольного элемента из библиотеки и число его обнаружений (0 - если элемент не обнаружен).
Номер контрольного элемента из библиотеки в первой строке равен 1, во второй - 2 и т.д.
Все числа в строках должны быть разделены пробелом.
Например, изображению на рис. 1 и контрольным элементам на рис. 2 соответствуют представленные ниже входной и выходной файлы.

рис. 1	рис. 2

Входной файл CONTROL.xx

8 7 4 4
1001
1111
1001
1001

1001
1001
1001
1001

0000
0000
0000
0000

0010
1111
0010
0010

1001001
1001001
1001001
1111111
1001001
1001001
1001001
1001001

Выходной файл Pnnnnn_6.xx
1 2
2 2
3 0
4 1

Решение g6_1038:
Классная задачка! Я больше нигде не видел входных файлов по 100 мегабайт! Ну, теперь перейдем к решению.
На разборе задач после олимпиады нам рассказали, как решить эту задачу (а частично я решил ее на олимпиаде, но тормозила она жутко) - но она была последней, а я перестал воспринимать информацию после 3 задачи :), так что придется мне рассказывать свое решение, которое я придумал сразу после окончания олимпиады :(.
Каждая вертикальная строка контрольного элемента состоит из произвольного количества нулей и единиц, причем общее количество этих нулей и единиц меньше либо равно 50. Эту последовательность можно считать двоичной записью числа, однако в Borland Pascal нет чисел такой размерности (про double, extended и т.п. молчу - т.к. они тормозят и не лезут в память), однако во Free Pascal, который предлагается на олимпиаде вместе с Borland Pascal, существует целочисленный тип данных int64 и ограничение в памяти помягче - 2Гб. Free Pascal вы можете скачать на официальном сайте freepascal.org - советую качать версию win32 или под Linux(если он у вас есть), потому что go32v2 глючит еще страшнее, чем две предыдущие. Во Free есть несколько особенностей - в конце надо ставить close(output), потому что автоматически он этого не делает, ставить скобки в арифметических выражениях, а то он иногда путает порядок действий (у меня такого не было - рассказали), и еще: int64 не поддерживает операции mod и не может быть использован как счетчик в цикле.
Итак, для каждой строки вычислим уникальное число, т.е. которое однозначно определяет именно эту строку. В случае если нам встретилась единица, то прибавляем к числу 1 и при каждой новой встретившейся цифре увеличиваем число вдвое. Вертикальной строке 1111 будет соответствовать число 15, строке 0001 - число 1 и т.п. Теперь каждый шаблон представлен L числами длиной до 50 двоичных цифр.
Проведем подобную операцию для первых L строк изображения - получим до 10000 чисел, каждое из которых длиной до 50 двоичных знаков. Теперь просто начнем поиск каждого шаблона (50 последовательных чисел) в строке (10000 последовательных чисел). Это, можно сказать, поиск подстроки в строке. Для ускорения этого процесса можно использовать хеш-функции. После того, как мы проверили все шаблоны, нам необходимо спуститься на одну строку вниз. Для этого из чисел строки больших либо равных 2^L вычитаем 2^L, т.е. убираем первую цифру. Теперь умножим полученные числа на 2 (освободим место для нового ряда. В случае если встретилась 1, то прибавим к числу строки 1. Так будем продолжать до конца входного файла.
Хотелось бы сказать, что заметное ускорение в работе даст использование вместо типизированного файла нетипизированного, т.к. Pascal читает из нетипизированного файла намного быстрее.
Скачать тесты к задаче