#include <bits/stdc++.h>
using namespace std;
#define M(X) (X % P + P) % P
template<typename T>
using V = vector<T>;
using ll = long long;
const ll P = 1000000007LL, A = 10007LL, B = 10009LL;
int n, m, ansl, ansr, lo, hi, mi, bi;
char c;
V<V<ll>> a, h;
V<ll> pa, pb, pia, pib;
ll inv;
ll exp(ll b, ll e) {
ll res = 1;
while (e != 0) {
if (e & 1) res = (res * b) % P;
b = (b * b) % P;
e >>= 1;
}
return res;
}
ll ch(ll a, ll b, ll c, ll d) {
return M(M(M(h[c][d] - (a - 1 >= 0 ? h[a - 1][d] : 0) - (b - 1 >= 0 ? h[c][b - 1] : 0) + (a - 1 >= 0 && b - 1 >= 0 ? h[a - 1][b - 1] : 0)) * pia[a]) * pib[b]);
}
int main() {
cin >> n >> m;
inv = exp(A, P - 2);
pa = pia = V<ll>(2 * n);
pa[0] = pia[0] = 1;
for (int i = 1; i < 2 * n; i++) {
pa[i] = M(pa[i - 1] * A);
pia[i] = M(pia[i - 1] * inv);
}
inv = exp(B, P - 2);
pb = pib = V<ll>(2 * m);
pb[0] = pib[0] = 1;
for (int i = 1; i < 2 * m; i++) {
pb[i] = M(pb[i - 1] * B);
pib[i] = M(pib[i - 1] * inv);
}
a = V<V<ll>>(2 * n, V<ll>(2 * m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> c;
if (c == '*') a[i][j] = 1;
if (c == '.') a[i][j] = 2;
a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
}
}
h = V<V<ll>>(2 * n, V<ll>(2 * m));
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < 2 * m; j++) {
h[i][j] = M((i > 0 ? h[i - 1][j] : 0)
+ (j > 0 ? h[i][j - 1] : 0)
- M((i > 0 && j > 0 ? h[i - 1][j - 1] : 0)
+ M(M(a[i][j] * pa[i]) * pb[j])));
}
}
ansl = ansr = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
lo = 0, hi = n;
while (lo < hi) {
mi = (lo + hi) / 2;
if (ch(ansl, ansr, ansl + mi, ansr + m - 1) == ch(i, j, i + mi, j + m - 1)) {
lo = mi + 1;
} else {
hi = mi;
}
}
bi = hi;
if (bi == n) continue;
lo = 0, hi = m - 1;
while (lo < hi) {
mi = (lo + hi) / 2;
if (ch(ansl, ansr, ansl + bi, ansr + mi) == ch(i, j, i + bi, j + mi)) {
lo = mi + 1;
} else {
hi = mi;
}
}
if (a[i + bi][j + hi] < a[ansl + bi][ansr + hi]) {
ansl = i;
ansr = j;
}
}
}
for (int ki = 0; ki < n; ki++) {
for (int kj = 0; kj < m; kj++) {
cout << (a[ansl + ki][ansr + kj] == 1 ? "*" : ".");
}
cout << '\n';
}
cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |