记录编号	120839	评测结果	AAAAAAAAAA
题目名称	[Ural 1486] 相等的正方形	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.012 s
提交时间	2014-09-16 22:06:44	内存使用	10.58 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL HS=1097159,P1=131,P2=2437;
const int SIZEN=501;
LL P1pow[SIZEN]={0},P2pow[SIZEN]={0};
int N,M;
char s[SIZEN][SIZEN];
bool hash[HS+1]={0};
int head[HS+1]={0};
int x[SIZEN*SIZEN]={0},y[SIZEN*SIZEN]={0};
int next[SIZEN*SIZEN]={0};
int tot;
LL line[SIZEN][SIZEN]={0};
int r1,c1,r2,c2;
LL realmod(LL x){
	x%=HS;
	if(x<0) x+=HS;
	return x;
}
void insert(int pos,int r,int c){
	x[tot]=r,y[tot]=c;
	next[tot]=head[pos];
	head[pos]=tot;
	tot++;
}
bool cmp(int r1,int c1,int r2,int c2,int r){//半径r
	for(int i=0;i<r;i++){
		for(int j=0;j<r;j++){
			if(s[r1+i][c1+j]!=s[r2+i][c2+j]) return false;
		}
	}
	return true;
}
void getline(int r){
	for(int i=1;i<=N;i++){
		LL temp=0;
		for(int j=1;j<=M;j++){
			temp=(temp*P1+s[i][j])%HS;
			if(j>r) temp=realmod(temp-P1pow[r]*s[i][j-r]);
			if(j>=r) line[i][j-r+1]=temp;
		}
	}
}
bool check(int i,int j,int pos,int r){
	pos=head[pos];
	while(pos!=-1){
		if(cmp(i,j,x[pos],y[pos],r)){
			r1=x[pos],c1=y[pos],r2=i,c2=j;
			return true;
		}
		pos=next[pos];
	}
	return false;
}
bool check_conflict(int r){
	if(!r) return true;
	getline(r);
	memset(hash,0,sizeof(hash));
	memset(head,-1,sizeof(head));
	memset(next,-1,sizeof(next));
	tot=0;
	for(int j=1;j<=M-r+1;j++){
		LL temp=0;
		for(int i=1;i<=N;i++){
			temp=(temp*P2+line[i][j])%HS;
			if(i>r) temp=realmod(temp-P2pow[r]*line[i-r][j]);
			if(i>=r){
				if(hash[temp]) if(check(i-r+1,j,temp,r)) return true;
				hash[temp]=true;
				insert(temp,i-r+1,j);
			}
		}
	}
	return false;
}
void work(void){
	int l=0,r=min(N,M);
	while(l<r){
		int mid=(l+r)>>1;
		if(check_conflict(mid+1)) l=mid+1;
		else r=mid;
	}
	check_conflict(l);
	printf("%d\n",l);
	/*if(l){
		printf("%d %d\n",r1,c1);
		printf("%d %d\n",r2,c2);
	}*/
}
void checkprime(int x){
	for(int i=2;i<x;i++) if(x%i==0) cout<<i<<endl;
}
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++) scanf("%s",&s[i][1]);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) s[i][j]-='a';
	P1pow[0]=P2pow[0]=1;
	for(int i=1;i<=N&&i<=M;i++) P1pow[i]=(P1pow[i-1]*P1)%HS,P2pow[i]=(P2pow[i-1]*P2)%HS;
}
int main(){
	freopen("equalsquares.in","r",stdin);
	freopen("equalsquares.out","w",stdout);
	read();
	work();
	return 0;
}