字符串专题：G - Milking Grid (二维kmp)

#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

*/