POJ2185 Milking Grid

题意

给出一个矩阵，求该矩阵的最小循环节面积。（不要求恰好完全覆盖）。

矩阵大小为 $N\times M$ ，$N\le 10000 \ , \ M\le 75$ 。

题解

对行和列分别求出 $next[]$ ，答案就是 $(n-next[n])\times (m-next[m])$ 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,m,nxt[10005];
char s[10005][80];

inline bool eqx(int x,int y) //判断行是否相等
{
    for (int i=1;i<=m;i++)
    {
        if (s[x][i]==s[y][i]) continue;
        return 0;
    }
    return 1;
}

inline bool eqy(int x,int y) //判断列是否相等
{
    for (int i=1;i<=n;i++)
    {
        if (s[i][x]==s[i][y]) continue;
        return 0;
    }
    return 1;
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
    nxt[1]=0;
    for (int i=2,j=0;i<=n;i++)
    {
        while (j && !eqx(i,j+1)) j=nxt[j];
        if (eqx(i,j+1)) j++;
        nxt[i]=j;
    }
    int ans=n-nxt[n];
    nxt[1]=0;
    for (int i=2,j=0;i<=m;i++)
    {
        while (j && !eqy(i,j+1)) j=nxt[j];
        if (eqy(i,j+1)) j++;
        nxt[i]=j;
    }
    ans*=(m-nxt[m]);
    return !printf("%d",ans);
}