#include <stdio.h> #include <string.h> #define MAX 10010 #define MIN 110 //题意:给定一个n*m的字符矩阵,每行字符会有若干个相同的串组成,最后一个重复串不一定要完整。问这个矩阵可由面积最小为多少的矩阵组成。 int len,next[MAX]; int row[MAX],col[MIN]; char str[MAX][MIN],rostr[MIN][MAX]; int Kmp(char *str) { int i,j,len; len = strlen(str); i = 0,j = -1; next[i] = -1; while (i < len) { if (j == -1 || str[i] == str[j]) i++,j++,next[i] = j; else j = next[j]; } return len - next[len];//公共串长度,(最后一个重复串不一定要完整) } int gcd(int a,int b){ return b==0 ? a: gcd(b,a%b); } int lcm(int n,int m) { return n / gcd(n,m) * m; } int main() { int i,j,k,m,n; int r,c; while (scanf("%d%d",&n,&m) != EOF) { r = c = 1; for (i = 0; i < n; ++i) { scanf("%s",str[i]); row[i] = Kmp(str[i]); } for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) rostr[j][i] = str[i][j];//倒转一下矩阵 for (j = 0; j < m; ++j) col[j] = Kmp(rostr[j]); for (i = 0; i < m; ++i) r = lcm(r,col[i]);//先由列判行,再由行判列(1 <= n <= 10,000 ,1 <= m <= 75) r = n < r ? n : r; for (i = 0; i < r; ++i)//最小重复矩阵一定在左上角,且不会超过r行。 c = lcm(c,row[i]); c = m < c ? m : c; printf("%d\n",r * c); } return 0; } /* Sample Input 5 15 ABCDABCDABCDABC BBABBABBABBABBA ABCDABCDABCDABC BBABBABBABBABBA ABCDABCDABCDABC 4 12 ABABABABABAB BBABBABBABBA ABABABABABAB BBABBABBABBA Sample Output 24 最小矩阵为: ABCDABCDABCD BBABBABBABBA col[0]:len-next[len]=5-3=2 col[1]:len-next[len]=5-4=1 c=lcm(col)=2*1=2; row[0]:len-next[len]=15-11=4; row[1]:len-next[len]=15-12=3; r=lcm(row)=4*3=12; 12 最小矩阵为: ABABAB BBABBA */