poj 2185

题意：给你一个字符矩阵，求出它的最小覆盖子矩阵，即使得这个子矩阵的无限复制扩张之后的矩阵，能包含原来的矩阵。 即二维的最小覆盖子串。

思路：KMP很好的一道题。首先易证：最小覆盖子矩阵一定靠左上角。那么，我们考虑求出每一行的最小重复串长度，所有行的最小重复串的长度的lcm就是最小重复子矩阵的宽。然后我们对列也做相同的操作。于是我们就可以求得最小重复子矩阵的大小了。（这里要注意一点：当所得的宽大于原来的宽时，就让等于原来的宽，长也如此）。算法实现：算法的核心在于高效的求出每一行和每一列的最小重复串，这个可以最原串做一次KMP中的get_next()。（注：以上部分为转载）

代码如下：

#include<iostream>
using namespace std;
const int rMax = 10002;
const int cMax = 77;

int row, col;
char map[rMax][cMax];

int get_next_c(int r)
{        //  对每一行求最小覆盖串。
    int next[cMax], j=1, k=0;
    next[0] = -1;
	next[1]=0;
    while(j< col)
	{
        if( map[r][j] == map[r][k])
		{
			next[j+1]=k+1;
			j++;
			k++;

        }
        else if (k==0)
        {
			next[j+1]=0;
			j++;
        }
		else
			k=next[k];
    }
    return j - next[j];
}

int get_next_r(int c)
{       //  对每一列求最小覆盖串。
    int next[rMax], j=1, k=0;
    next[0] = -1;
	next[1]=0;
    while(j< row)
	{
        if( map[j][c] == map[k][c])
		{
			next[j+1]=k+1;
			j++;
			k++;
        }
		else if (k==0)
		{
			next[j+1]=0;
			j++;
		}
        else k= next[k];
    }
    return j- next[j];
}

int lcm(int a, int b)
{      //  求a,b的最小公倍数lcm。这个模板应该学。
    int mul = a * b;
    int r = a % b;
    while(r)
	{
        a = b;
        b = r;
        r = a % b; 
    }
    return mul / b;         //  最小公倍数 * 最大公约数 = a * b。
}

int main()
{
    int r, c, ans_r = 1, ans_c = 1;
    scanf("%d%d", &row, &col);
    for(r = 0; r < row; r ++)    //  改逐个输入为逐行输入，从700MS优化到100MS，汗.....
        scanf("%s", map[r]);
    for(r = 0; r < row; r ++)
	{
        ans_c = lcm(ans_c, get_next_c(r));
        if(ans_c > col)
		{         //  注意! 当所得的宽大于原来的宽时，就让等于原来的宽,WA在了这里。
            ans_c = col; 
            break;
        }
    }
    for(c = 0; c < ans_c; c ++)
	{
        ans_r = lcm(ans_r, get_next_r(c));
        if(ans_r > row)
		{
            ans_r = row; 
            break;
        }
    }
    printf("%d\n", ans_r * ans_c);
    return 0;
}