poj 2185 Milking Grid（next数组求最小循环节）

题意：求最小的循环矩形

思路：分别求出行、列的最小循环节，乘积即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int next[10005];
int r,c;
char str[10005][80];

bool equalR(int i,int j){//行相等
    int k;
    for(k=0;k<c;++k)
        if(str[i][k]!=str[j][k])return false;
    return true;
}

bool equalC(int i,int j){//列相等
    int k;
    for(k=0;k<r;++k)
        if(str[k][i]!=str[k][j])return false;
    return true;
}

void GetNext1(){//求next数组（行
    int j,k;//,len;
    j=0;
    k=-1;
    next[0]=-1;
    //len=strlen(str);
    while(j<r){
        if(k==-1||equalR(j,k)){
            ++j;
            ++k;
            next[j]=k;//此句可由优化替代
            /*优化（仅保证求KMPIndex时可用。谨慎使用。）
            if(t[j]!=t[k])next[j]=k;
            else next[j]=next[k];
            */
        }
        else k=next[k];
    }
}

void GetNext2(){//求next数组（列
    int j,k;//,len;
    j=0;
    k=-1;
    next[0]=-1;
    //len=strlen(str);
    while(j<c){
        if(k==-1||equalC(j,k)){
            ++j;
            ++k;
            next[j]=k;//此句可由优化替代
            /*优化（仅保证求KMPIndex时可用。谨慎使用。）
            if(t[j]!=t[k])next[j]=k;
            else next[j]=next[k];
            */
        }
        else k=next[k];
    }
}

int main(){
    int i,len,a,b;
    while(~scanf("%d%d",&r,&c)){
        for(i=0;i<r;++i)scanf("%s",str[i]);
        GetNext1();
        a=r-next[r];//行最小循环节
        GetNext2();
        b=c-next[c];//列最小循环节
        printf("%d
",a*b);
    }
    return 0;
}