首页 > 代码库 > poj2185 Milking Grid（KMP运用）

poj2185 Milking Grid（KMP运用）

2024-07-17 10:09:18   217人阅读

题目链接：http://poj.org/problem?id=2185


Milking Grid
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 6249 Accepted: 2616

Description

Every morning when they are milked, the Farmer John‘s cows form a rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <= 75) columns. As we all know, Farmer John is quite the expert on cow behavior, and is currently writing a book about feeding behavior in cows. He notices that if each cow is labeled with an uppercase letter indicating its breed, the two-dimensional pattern formed by his cows during milking sometimes seems to be made from smaller repeating rectangular patterns. 

Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below. 

Input

* Line 1: Two space-separated integers: R and C 

* Lines 2..R+1: The grid that the cows form, with an uppercase letter denoting each cow‘s breed. Each of the R input lines has C characters with no space or other intervening character. 

Output

* Line 1: The area of the smallest unit from which the grid is formed 

Sample Input

2 5
ABABA
ABABA

Sample Output

2

Hint

The entire milking grid can be constructed from repetitions of the pattern ‘AB‘.

Source

USACO 2003 Fall

思路：

求出每一行的最小重复子串的长度，所有行的最小重复串的长度的LCM就是最小重复子矩阵的宽。然后对列也做相同的操作。于是就可以求得最小重复子矩阵的大小了。（这里要注意一点：当所得的宽大于原来的宽时，就让等于原来的宽，长也是如此）。


代码如下：

#include<cstdio>
#include<cstring>
#define MAXN 10017
int next[MAXN];
int len;
int row, col;
int subrow[MAXN];
int subcol[87];
char s[MAXN][87];

int LCM(int a, int b)//最小公倍数
{
    int x = a, y = b;
    int r = x%y;
    while(r > 0)
    {
        x = y;
        y = r;
        r = x % y;
    }
    return a*b/y;
}

int getnext_r(int r)//行
{
    int i = 0, j = -1;
    next[0] = -1;
    while(i < col)
    {
        if(j == -1 || s[r][i] == s[r][j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
    return col - next[col];
}
int getnext_c(int c)//列
{
    int i = 0, j = -1;
    next[0] = -1;
    while(i < row)
    {
        if(j == -1 || s[i][c] == s[j][c])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
    return row - next[row];
}
int main()
{
    while(~scanf("%d%d",&row, &col))
    {
        for(int i = 0; i < row; i++)
        {
            scanf("%s",s[i]);
        }
        for(int i = 0; i < row; i++)//统计每一行的重复子串
        {
            subrow[i] = getnext_r(i);
        }
        for(int i = 0; i < col; i++)//统计每一列的重复子串
        {
            subcol[i] = getnext_c(i);
        }
        int R = 1;
        for(int i = 0; i < row; i++)//统计所有行的重复子串的最小公倍数
        {
            R = LCM(R,subrow[i]);
        }
        if(R > col)//如果最小公倍数大于了列数就取列数
            R = col;
        int C = 1;
        for(int i = 0; i < col; i++)//统计所有列的重复子串的最小公倍数
        {
            C = LCM(C,subcol[i]);
        }
        if(C > row)//如果最小公倍数大于了行数就取行数
            C = row;
        int ans = R * C;
        printf("%d\n",ans);
    }
    return 0;
}




联系
我们