poj2185 Milking Grid (最小覆蓋矩陣)
//給定一個由字符組成的矩陣,求出它的面積最小的覆蓋矩陣
//可以求出每一行的最小覆蓋子串的長度,只要對這些長度求最小公倍數,就可以獲得最小覆蓋矩陣的寬度。
//同理,求出每一列的最小覆蓋子串的長度,再求最小公倍數,就可以獲得最小覆蓋矩陣的高度了。
# include
# include
# include
using namespace std;
char a[10010][100];
int next[10010];
int n,m;
int Getnext1(int r)
{
int i=0,j=-1;
next[0]=-1;
while(i<=m)
{
if(j==-1||a[r][i]==a[r][j])
i++,j++,next[i]=j;
else
j=next[j];
}
return m-next[m];
}
int Getnext2(int r)
{
int i=0,j=-1;
next[0]=-1;
while(i<=n)
{
if(j==-1||a[i][r]==a[j][r])
i++,j++,next[i]=j;
else
j=next[j];
}
return n-next[n];
}
int lcm(int a,int b)//最小公倍數模版
{
int mul = a * b;
int r = a % b;
while(r)
{
a = b;
b = r;
r = a % b;
}
return mul / b;
}
int main()
{
int i,ans2,ans1;
while(~scanf("%d%d",&n,&m))
{
for(i=0; im)
{
ans1=m;
break;
}
}
for(i=0; in)
{
ans2=n;
break;
}
}
printf("%d\n",ans1*ans2);
}
return 0;
}