Ремонт#18

Ремонт (Розбір)

Полоса шпалер циклічна: щоб отримати повний малюнок, прямокутник N \times M повторюється ліворуч і праворуч. Тому зсув другої полоси праворуч на клітинок — це циклічний зсув кожного її рядка.

Запишемо умову формально. Після зсуву на у стовпці другої полоси опиниться символ, що стояв у стовпці (j - k) \bmod M. Малюнки збігаються, коли для кожного рядка і кожного стовпця

\mathrm{first}_i[j] = \mathrm{second}_i[(j - k) \bmod M].

Іншими словами, рядок першої полоси має бути циклічним зсувом відповідного рядка другої.

Класичний прийом для циклічних зсувів: шукати рядок першої полоси як підрядок у подвоєному рядку другої, тобто в \mathrm{second}_i + \mathrm{second}_i. Кожне входження на позиції (де 0 \le o < M) означає, що \mathrm{first}_i[j] = \mathrm{second}_i[(o+j) \bmod M], а отже відповідає зсуву k = (M - o) \bmod M.

Пошук усіх входжень робиться алгоритмом КМП за лінійний час. Для кожного рядка отримуємо множину допустимих зсувів; шуканий має підходити всім рядкам одночасно, тому множини треба перетнути. Зручно завести масив-лічильник довжини : для кожного рядка збільшуємо лічильник кожного його допустимого зсуву, а наприкінці шукаємо найменший , у якого лічильник дорівнює .

Складність — , тобто до 2 \cdot 10^6 операцій при N \le 20 і M \le 10^5. Умова гарантує, що відповідь існує, тому окремо обробляти її відсутність не потрібно.