# Vệ tinh
Nguồn: tham khảo bài ôn tập thi HSG của thầy Đặng Trung Kiên.

Rating: 1800.

## Đề bài

Cho vệ tinh bay xung quanh Sao Thổ và có thể chụp ảnh núi lửa từ các góc độ khác nhau. Hình ảnh chụp có dạng một ma trận gồm $N$ hàng và $M$ cột, trong đó kí tự $*$ biểu thị núi lửa và kí tự $.$ biểu thị đồng bằng. Ta nói rằng hai hình ảnh tương ứng với cùng một vệ tinh nếu một hình ảnh có thể được lấy từ hình ảnh kia bằng cách dịch chuyển vòng tròn theo hàng và cột.

#### Yêu cầu:
Ta nối tất cả các hàng của ma trận thành một xâu, hình ảnh nhỏ nhất theo thứ tự từ điển khi xâu tương ứng với nó có thứ tự từ điển nhỏ nhất. Tìm hình ảnh có thứ tự từ điển nhỏ nhất.

## Input:

- Dòng đầu chứa hai số $N$, $M$ ($1 \le N, M \le 10^{3}$).
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ kí tự được viết liền nhau là $.$ hoặc $*$.

## Output

- Gồm một bảng $N \times M$ là bảng có thứ tự từ điển nhỏ nhất sau biến đổi.

## Sample


## Giới hạn

- Subtask 1:($30\%$) $1 \le N, M \le 50$.
- Subtask 2:($30\%$) $1 \le N, M \le 300$.
- Subtask 3:($40\%$) Không có giới hạn gì thêm.

## Lời giải:

<details>
<summary>Lời giải</summary>

Từ mảng $A$ cỡ $N \times M$ ta tạo mảng $B$ có cỡ $2N \times 2M$ bằng cách ghép $4$ mảng $A$ lại như sau:
[](https://hackmd.io/_uploads/S1BDU1A1a.png)

Nhận thấy mỗi các mảng con có kích thước $nN \times M$ của mảng $B$ tương ứng sẽ là hình ảnh của mảng $A$ sau một số phép biến đổi.
Ta chỉ cần tìm mảng con có kích thước $N \times M$ trong mảng $B$ mà có thứ tự từ điển nhỏ nhất.
Giả sử ta có 2 mảng C và D để so sánh xem xâu nào có thứ tự từ điển nhỏ hơn ta làm như sau:
- Ta tính hash trong mỗi hàng. Coi mỗi hàng là một phần từ ta sẽ tính hash cho cả bảng và coi hàng $1$ là ký tự đầu tiên.
- Tìm $i$ lớn nhất sao cho $i$ hàng đầu của $2$ mảng giống nhau.
- Tìm $j$ lớn nhất sao cho $j$ ký tự đầu tiên của hàng thứ $i + 1$ mỗi bảng giống nhau.
- Ta có thể tìm nhanh $i$ và $j$ bằng tìm kiếm nhị phân.
- Nếu $C_{ij} > D_{ij}$ thì C lớn hơn và ngược lại

Cuối cùng ta chỉ cần duyệt tất cả mảng con cỡ $N \times M$ của $B$ và tìm xâu nhỏ nhất

</details>

<details>
<summary>Code </summary>

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const ll N = 2e3 + 3;
ll n, m, i, j, a[N][N], b[N][N];
ll base = 137, mod = 1e9 + 7, L, R;
ll p[N], h[N][N];

ll get(ll i, ll l, ll r) {
    return (h[i][r] - h[i][l - 1] * p[r - l + 1] % mod + mod) % mod;
}

ll Get(ll i, ll l, ll r) {
    return (b[i][r] - b[i][l - 1] * p[r - l + 1] % mod + mod) % mod;
}

ll check(ll x, ll y, ll u, ll v) {
    ll l = 1, r = n, z = 0, Z = 0;
    while (l <= r) {
        ll mid = (l + r) / 2;
        ll X = Get(y, x, x + mid - 1);
        ll Y = Get(v, u, u + mid - 1);
        if (X == Y) {
            z = max(z, mid);
            l = mid + 1;
        } 
        else r = mid - 1;
    }
    z++;
    if (z == n + 1) return 0;
    
    l = 1; r = m;
    while (l <= r) {
        ll mid = (l + r) / 2;
        ll X = get(x + z - 1, y, y + mid - 1);
        ll Y = get(u + z - 1, v, v + mid - 1);
        if (X == Y) {
            Z = max(Z, mid);
            l = mid + 1;
        } 
        else r = mid - 1;
    }
    Z++;
    if (Z == m + 1) return 0;
    return ((a[x + z - 1][y + Z - 1] > a[u + z - 1][v + Z - 1])? 1:0);
}

int main() {
    cin >> n >> m;
    for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) {
        char c;
        cin >> c;
        a[i][j] = (c == '.');
    }
    
    for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) 
        a[i][j + m] = a[i][j];
    for (i = 1; i <= n; i++)
    for (j = 1; j <= 2 * m; j++) 
        a[i + n][j] = a[i][j];
    
    p[0] = 1;
    for (i = 1; i < N; i++) 
        p[i] = p[i - 1] * base % mod;
    for (i = 1; i <= 2 * n; i++)
        for (j = 1; j <= 2 * m; j++) 
            (h[i][j] = h[i][j - 1] * base % mod + a[i][j]) % mod;
    
    L = R = 1;
    for (j = 1; j <= m; j++) {
        for (i = 1; i <= 2 * n; i++) {
            ll z = get(i, j, j + m - 1);
            b[j][i] = (b[j][i - 1] * base % mod + z) % mod;
        }
        for (i = 1; i <= n; i++) 
            if(check(L, R, i, j)) {
                L = i;
                R = j;
            }
    }
    
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) 
            cout << ((a[i + L - 1][j + R - 1] == 1)? '.':'*'); 
        cout << '\n';
    }
    
    return 0;
}

</details>