Rockdu's Blog

【题目描述】

给出一个 n × m 的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵 中出现了至少两次。输出最大正方形的边长。

【输入】

第一行两个整数 n, m 代表矩阵的长和宽；

接下来 n 行，每行 m 个字符（小写字母） ，表示矩阵。

【输出】

输出一个整数表示满足条件的最大正方形的边长。

【输入样例】

5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl

【输出样例】

3

【提示】

【数据规模】

对于 30%的数据，n,m≤100；

对于 100%的数据，n,m≤500。

对于本题，我们可以这样哈希：选择一个进制数base，一次从左到右从上到下给每一个方格都分配一个base^k。这样有什么好处呢？首先，这个哈希的正确性是对的，不会有重复。其次，如果要提取一个矩形的哈希值，我们只需要对矩阵做前缀和，减出这个矩阵对应的哈希值。但是不同位置的相同矩阵哈希值会不一样。那么我们只需要把它们都“移到左上角“就行了——乘以询问矩阵左上角base^k的逆元。我们就可以O(1)判断两个矩阵是否相同了。

但是n^3是没有办法卡过去的，这样我们想到二分正方形的边长，就可以变为O(n^2 * logn)

代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
const int maxn = 505, base[2] = {555, 233}, P[2] = {6662333, 100000007};
struct node {int k2, next;}e[maxn * maxn];
int head[6662333 + 5];
char s[maxn][maxn];
int n, m, larger, Bpow[2][maxn][maxn], Binv[2][maxn][maxn];
int Pref[2][maxn][maxn], now[2], key, cnt;

void adde(const int &u, const int &k2) {
	e[++cnt] = (node) {k2, head[u]};
	head[u] = cnt;
}

LL fpow(LL a, int b, int p) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = (ans * a) % p;
		b >>= 1, a = a * a % p;
	}
	return ans;
}

int GetMtr(int a, int b, int c, int d, int st) {
	int ans;
	ans = (Pref[st][c][d] - Pref[st][c][b - 1] - Pref[st][a - 1][d] + Pref[st][a - 1][b - 1] + P[st] * 2) % P[st];
	ans = 1LL * ans * Binv[st][a][b] % P[st];
	return ans;
}

bool Fdk(int k) {
	memset(head, 0, sizeof(head)), cnt = 0;
	for(register int i = 1; i <= n - k; ++i) {
		for(register int j = 1; j <= m - k; ++j) {
			now[0] = GetMtr(i, j, i + k, j + k, 0);
			now[1] = GetMtr(i, j, i + k, j + k, 1);
			for(register int u = head[now[0]]; u; u = e[u].next)
				if(now[1] == e[u].k2) return 1;
			adde(now[0], now[1]);
		}
	}
	return 0;
}

int DC(int l, int r) {
	while(l < r - 1) {
		int mid = l + r >> 1;
		if(Fdk(mid)) l = mid;
		else r = mid;
	}
	return l;
}

int main() {
	//freopen("test.in", "r", stdin);
	scanf("%d%d", &n, &m), larger = max(n, m);
	Bpow[0][0][m] = fpow(base[0], P[0] - 2, P[0]), Bpow[1][0][m] = fpow(base[1], P[1] - 2, P[1]);
	for(register int st = 0; st <= 1; ++st)	
		for(register int i = 1; i <= n; ++i) {
			Bpow[st][i][1] = 1LL * Bpow[st][i - 1][m] * base[st] % P[st], Binv[st][i][1] = fpow(Bpow[st][i][1], P[st] - 2, P[st]); 
			for(register int j = 2; j <= m; ++j) {
				Bpow[st][i][j] = 1LL * Bpow[st][i][j - 1] * base[st] % P[st];
				Binv[st][i][j] = fpow(Bpow[st][i][j], P[st] - 2, P[st]);
			}
		}
	for(register int i = 1; i <= n; ++i)
		scanf("%s", s[i] + 1);
	for(register int st = 0; st <= 1; ++st)
		for(register int i = 1; i <= n; ++i) {
			for(register int j = 1; j <= m; ++j) {
				Pref[st][i][j] = (Pref[st][i][j - 1] + Pref[st][i - 1][j] - Pref[st][i - 1][j - 1] + P[st]) % P[st];
				Pref[st][i][j] = (Pref[st][i][j] + 1LL * s[i][j] * Bpow[st][i][j] % P[st]) % P[st];
			}
		}
	printf("%d", DC(-1, min(n, m) + 1) + 1);
	return 0;
}