POJ 2185 Milking Grid（KMP最小循环节）

http://poj.org/problem?id=2185

题意：

给出一个r行c列的字符矩阵，求最小的覆盖矩阵可以将原矩阵覆盖，覆盖矩阵不必全用完。

思路：

我对于字符串的最小循环节是这么理解的：

如果next[12]=5，那么前5个前缀字符和后5个后缀字符是一样，但是此时还需要加上中间的2个，所以循环节为7。

如果next[12]=7，那么中间2个既出现在了前缀里，也出现在了后缀里，所以中间的2个字符等于开头的两个字符。此时循环节为5。

这样的话，字符串的最小循环节就是 len - next[len] 。

那么这道题的话：

对每一行求最小循环节，并对所有行求最小公倍数。

对每一列求最小循环节，并对所有列求最小公倍数。

相乘得最小面积。

注意：

如果此时的最小公倍数大于了行或列，可以直接等于行或列并退出了。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 using namespace std;

 const int maxn=+;

 int r,c;

 char str[][];

 int next[];

 int gcd(int a,int b)

 {

     return b==?a:gcd(b,a%b);

 }

 void get_nextrow(int r)

 {

     int i=-,j=;

     next[]=-;

     while(j<c)

     {

         if(i==- || str[r][i]==str[r][j])

             next[++j]=++i;

         else

             i=next[i];

     }

 }

 void get_nextcol(int c)

 {

     int i=-,j=;

     next[]=-;

     while(j<r)

     {

         if(i==- || str[i][c]==str[j][c])

             next[++j]=++i;

         else

             i=next[i];

     }

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     scanf("%d%d",&r,&c);

     for(int i=;i<r;i++)

         scanf("%s",&str[i]);

     int row=;

     for(int i=;i<r;i++)

     {

         get_nextrow(i);

         row=row*(c-next[c])/gcd(row,c-next[c]);

         if(row>=c)

         {

             row=c;

             break;

         }

     }

     int col=;

     for(int i=;i<c;i++)

     {

         get_nextcol(i);

         col=col*(r-next[r])/gcd(col,r-next[r]);

         {

             if(col>=r)

             {

                 col=r;

                 break;

             }

         }

     }

     printf("%d\n",row*col);

 }

巴特西

POJ 2185 Milking Grid（KMP最小循环节）

最新文章

热门文章