| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:soIn Reply To:so Posted by:tayu at 2005-10-10 14:53:48 #include<iostream>
#include<cstring>
using namespace std;
char mat[10001][100];
int next[10005];
int r,c;
inline char getc(int p,bool dec,int k){
if(dec)
return mat[k][p];
else return mat[p][k];
}
int getpows(int p,bool dec){//1 c 0 r
int n;
if(dec)n=r;
else n=c;
next[0]=-1;int i,j;
for(i=1,j=-1;i<n;i++)
{
while(j>-1&&getc(p,dec,j+1)!=getc(p,dec,i))j=next[j];
if(getc(p,dec,j+1)==getc(p,dec,i))j++;
next[i]=j;
}
return n-1-next[n-1];
}
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
int main(){
// freopen("0.txt","r",stdin);
// freopen("1.txt","w",stdout);
scanf("%d%d",&r,&c);
int i,j;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
scanf(" %c",&mat[i][j]);
int res=1;
int ans=1;
for(i=0;i<r;i++)
ans=min(c,lcm(ans,getpows(i,0)));
res*=ans;ans=1;
for(i=0;i<c;i++)
ans=min(r,lcm(ans,getpows(i,1)));
res*=ans;
printf("%d\n",res);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator