poj2185:http://poj.org/problem?id=2185
题意：在一个字符矩阵中，找一个最小的字符子矩阵，使其能够覆盖整个矩阵。
题解：在KMP中i-next[i]是这能够覆盖这个串的最小串长度。所以这一题可以用KMP搞。对于每一行求一个最小覆盖，然后取其最小公倍数，如果最大的那个覆盖的2倍不小于串的的长度，那么此时应该取这个长度。然后列也是这个处理，最后把两个数乘起来就是要找的面积。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10005
using namespace std;
int next[N];
int n,m;
char s1[N];//模板串
char s2[N];//主串
int len1,len2;
int ans1,ans2;
char str1[N][];
void getnext(int plen){
int i = ,j = -;
next[]=-;
while( i<plen ){
if(j==-||s1[i]==s1[j]){
++i;++j;
// if(s1[i]!=s1[j] )
next[i] = j;
// else
// next[i] = next[j];
}
else
j = next[j];
}
}
int gcd(int a, int b){
if(b==)
return a;
return gcd(b,a%b);
} int lcm(int a, int b){//两个数的最小公倍数
return a*b/gcd(a, b);
}
int main(){
while(~scanf("%d%d",&n,&m)){
ans1=;
ans2=;
int maxn=;
for(int i=;i<=n;i++){
scanf("%s",s1);
strcpy(str1[i],s1);
getnext(m);
// printf("**%d\n",m-next[m]);
maxn=max(maxn,m-next[m]);
ans1=lcm(ans1,m-next[m]);
}
for(int i=;i<m;i++){
for(int j=;j<=n;j++){
s1[j-]=str1[j][i];
}
getnext(n); ans2=lcm(ans2,n-next[n]);
}
if(maxn*>=m)ans1=maxn;
else if(ans1>m)ans1=m;
if(ans2>n)ans2=n;
printf("%d\n",ans1*ans2);
}
}