Полоса шпалер циклічна: щоб отримати повний малюнок, прямокутник N \times M повторюється ліворуч і праворуч. Тому зсув другої полоси праворуч на клітинок — це циклічний зсув кожного її рядка.
Запишемо умову формально. Після зсуву на у стовпці другої полоси опиниться символ, що стояв у стовпці (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. Умова гарантує, що відповідь існує, тому окремо обробляти її відсутність не потрібно.