poj 2185 Milking Grid
求最小重复矩阵。
首先得证明一个结论，最小重复矩阵一定是靠着左上角的。这个可以利用黏贴技术证明。如果有一个不靠左上角的重复矩阵，必然可以通过黏贴得到一个大小相同的靠左上角的矩阵，这个自己画画就明白了。
第二个就是s=len-next[len]等于一个字符串的最小循环节。至于它是循环节利用画图可以看出来。
至于是最小的可以这么考虑，如果存在更小的循环节，必然能得到更大的next值，与next数组矛盾。
还有一点不是s的整数倍的必然不是循环节。
但是此题麻烦的地方在于，可以黏贴在空白的地方。这个需要对多出来的部分再次求循环节。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e4+9,maxm=80;
char a[maxn][maxm],b[maxm][maxn];
int count[maxn],next[maxn];
int n,m;
void kmp(char a[],int n)
{
next[0]=0;
next[1]=0;
for(int i=2;i<=n;i++)
{
int t=i-1;
while(t&&a[i]!=a[next[t]+1])
t=next[t];
next[i]=next[t]+(a[i]==a[next[t]+1]);
}
}
void work(char a[],int n)
{
kmp(a,n);
int t=n-next[n];
int ret=0,len=n;
while(ret+t!=n)
{
for(int i=t;i+ret<=n;i+=t)
count[i+ret]++;
ret+=len/t*t;
len=len-len/t*t;
t=len-next[len];
}
count[n]++;
}
void solve()
{
int c,r;
memset(count,0,sizeof(count));
for(int i=1;i<=n;i++)
work(a[i],m);
for(int i=1;i<=m;i++)
if(count[i]>=n)
{
c=i;
break;
}
memset(count,0,sizeof(count));
for(int i=1;i<=m;i++)
work(b[i],n);
for(int i=1;i<=n;i++)
if(count[i]>=m)
{
r=i;
break;
}
printf("%d\n",c*r);
}
int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[j][i]=a[i][j];
solve();
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e4+9,maxm=80;
char a[maxn][maxm],b[maxm][maxn];
int count[maxn],next[maxn];
int n,m;
void kmp(char a[],int n)
{
next[0]=0;
next[1]=0;
for(int i=2;i<=n;i++)
{
int t=i-1;
while(t&&a[i]!=a[next[t]+1])
t=next[t];
next[i]=next[t]+(a[i]==a[next[t]+1]);
}
}
void work(char a[],int n)
{
kmp(a,n);
int t=n-next[n];
int ret=0,len=n;
while(ret+t!=n)
{
for(int i=t;i+ret<=n;i+=t)
count[i+ret]++;
ret+=len/t*t;
len=len-len/t*t;
t=len-next[len];
}
count[n]++;
}
void solve()
{
int c,r;
memset(count,0,sizeof(count));
for(int i=1;i<=n;i++)
work(a[i],m);
for(int i=1;i<=m;i++)
if(count[i]>=n)
{
c=i;
break;
}
memset(count,0,sizeof(count));
for(int i=1;i<=m;i++)
work(b[i],n);
for(int i=1;i<=n;i++)
if(count[i]>=m)
{
r=i;
break;
}
printf("%d\n",c*r);
}
int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[j][i]=a[i][j];
solve();
}
return 0;
}
补充：软件开发 , C++ ,
