题意：给你一个字符矩阵，求出它的最小覆盖子矩阵，即使得这个子矩阵的无限复制扩张之后的矩阵，能包含原来的矩阵。 即二维的最小覆盖子串。
和HDOJ1358 Period 一样，对于(1….x)串x-next[x]就是它自身的最小覆盖串，所以可以把每行的所有覆盖求出来，找到他们的最小值，
即是最小覆盖子矩阵的宽，一些博客把每行的所有最小覆盖的公倍数求了出来，这样的确可以覆盖整个矩阵但不是最小覆盖子矩阵，是充分不必要条件，比如
2 8ABCDEFABAAAABAAA
答案是6，不是8
同理再找高即可这样的复杂度有点高，可以把宽找到后，把每行字符串当作“字符”再进行kmp：
//1008 KB172 ms#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int r,c,comwid,comhigh;char mapp[10100][80];int cnt[80],next[80];char s[80];int nexthigh[10100];void getnext(char str[]){int i=0;int j=next[0]=-1;while(str[i]!=0){while(j>-1&&str[i]!=str[j])j=next[j];j++;i++;next[i]=j;}}void getnexthigh(){int i=1;int j=nexthigh[1]=0;while(i<r+1){while(j>0&&strcmp(mapp[i],mapp[j]))j=nexthigh[j];i++;j++;nexthigh[i]=j;}}int main(){scanf("%d%d",&r,&c);for(int i=1;i<=r;i++){scanf("%s",mapp[i]);strcpy(s,mapp[i]);getnext(mapp[i]);int minsub= c-next[c];cnt[minsub]++;for(int j=c-1;j>minsub;j–){s[j]=0;int y=0;for(int x=0;mapp[i][y];x++,y++){if(!s[x]) x=0;if(s[x]!=mapp[i][y]) break;}if(!mapp[i][y]) cnt[j]++;}}cnt[c]=r;for(int i=1;i<=c;i++)if(cnt[i]==r){comwid=i;break;}for(int i=1;i<=r;i++)mapp[i][comwid]=0;getnexthigh();comhigh= r-(nexthigh[r+1]-1);printf("%d\n",comhigh*comwid);return 0;}其实同理上面那个把字符串整个kmp的优化，求宽的时候也可以把字符串整个kmp，，同样的道理，这样代码就变得简洁高效了：
//田神代码 1948 KB63 ms//思路：/*1.把每行字符串看作一个整体对行求next数组2.将矩阵转置3.进行操作1，注意这里的行是原来的列，列是原来的行，相当于求原来列的next数组4.求出len－next[len]即最小不重复子串的长度作为子矩形的边长*/#include <cstdio>#include <cstring>char s[10005][80], rs[80][10005];int R[10005], C[10005];int r, c;void get_nextR(){R[0] = -1;int j = -1, i = 0;while(i < r){if(j == -1 || strcmp(s[i], s[j]) == 0){i++;j++;R[i] = j;}elsej = R[j];}}void get_nextC(){C[0] = -1;int j = -1, i = 0;while(i < c){if(j == -1 || strcmp(rs[i], rs[j]) == 0){i++;j++;C[i] = j;}elsej = C[j];}}int main(){while(scanf("%d %d", &r, &c) != EOF){for(int i = 0; i < r; i++)scanf("%s", s[i]);get_nextR();for(int i = 0; i < r; i++)for(int j = 0; j < c; j++)rs[j][i] = s[i][j];get_nextC();printf("%d\n", (r – R[r]) * (c – C[c]));}}
学会宽容，要有一颗宽容的爱心！
