Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:so

Posted by zjut020 at 2010-03-03 22:12:31 on Problem 2185
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator