题目描述
blablabla
样例
blablabla
来一发快的题解
先求出每一行所有循环节并用桶统计个数,最后有r个的循环节即为行的解,用时$O(nm)$
同理可求出列的解,用时也为$O(nm)$
总时间复杂度$O(nm)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxR=1e4+5;
const int maxC=80;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
int main() {
char matrix[maxR][maxC];
ios::sync_with_stdio(false);
cin.tie(0);
ll r,c,next[maxR],i,j,minL,minH,k,l,ite,here,temp;
int storeC[maxC],storeR[maxR];
cin>>r>>c;
for(i=0;i<r;i++){
for(j=0;j<c;j++){
cin>>matrix[i][j];
}
}
next[0]=-1;
minL=0;
memset(storeC,0,sizeof(storeC));
memset(storeR,0,sizeof(storeR));
for(i=0;i<r;i++){
next[0]=-1;
for(j=1;j<=c;j++){
ite=j-1;
while (next[ite]!=-1&&matrix[i][j-1]!=matrix[i][next[ite]]){
ite=next[ite];
}
next[j]=next[ite]+1;
}
temp=c;
while (next[temp]!=-1){
storeC[c-next[temp]]++;
temp=next[temp];
}
}
minH=0;
for(i=0;i<c;i++){
next[0]=-1;
for(j=1;j<=r;j++){
ite=j-1;
while (next[ite]!=-1&&matrix[j-1][i]!=matrix[next[ite]][i]){
ite=next[ite];
}
next[j]=next[ite]+1;
}
temp=r;
while (next[temp]!=-1){
storeR[r-next[temp]]++;
temp=next[temp];
}
}
for(i=1;i<=c;i++){
if(storeC[i]==r){
minH=i;
break;
}
}
for(i=1;i<=r;i++){
if(storeR[i]==c){
minL=i;
break;
}
}
printf("%lld",minH*minL);
return 0;
}