NKOJ 2244 奶牛阵列（KMP+Hash）

发表于 |
字数统计: 789字 | 阅读时长 ≈ 3min

2244奶牛阵列

问题描述

每天早晨约翰的奶牛都会在挤奶的时候排成阵列，即站成R(1<=R<=10000)行C(1<=C<=75)列的矩阵。我们知道，约翰是奶牛专家，他打算写一本关于喂养奶牛的书，他发现，当奶牛按不同血统标记以后，整个大矩阵就像由很多小矩阵无缝拼接的一样。

请帮助约翰找到面积最小的模型矩阵，使他能拼出整个大矩阵，当然，模型矩阵的尺寸不一定能整除大矩阵，也就是说你可以用若干个模型矩阵，拼出一个包含大矩阵的更大的矩阵。

输入格式

第一行， 两个整数R和C
接下来是由大写字母构成的R*C的矩阵

输出格式

一个整数，表示最小模型矩阵的面积。

样例输入

2 5
ABABA
BABAB

样例输出

4

提示

样例说明：
模型矩阵如下：
AB
BA
拼出的大矩阵如下：
ABABAB
BABABA

本题usaco官方数据很弱，很多错解可以AC，下面提供两种正确思路。

思路一：

首先明确小矩阵不能够重叠，所以我们考虑循环节。
一个简单的想法是求出每一行和每一列的分别的最小循环节，然后求最小公倍数，把行和列的最小公倍数乘起来，然而这并不是最优解，因为循环节可能有多个，比如
AAABCAAA
ABABABAB
这样的数据，两行的最小循环节的最小公倍数是10，算出答案20，然而显然正解是12。
所以我们需要求出每一行所有的循环节，然后求出他们取不同循环节时最小的最小公倍数。
观察可以发现只需要取所有行的最小公共循环节长度即可（因为循环节的倍数也是循环节）。列的处理同理。

思路二：

将每一行Hash成一个数字，然后求形成数列的最小循环节，列同理，然后将两个最小循环节长度乘起来就是答案。这样相当求出了最小循环矩形。

思路二代码（By rgnoH）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>
#define ll long long
#define mod 0xffff
int R,C,fail[10005],rans,cans;
ll Hash[10005];
char ch[10005][80];

int main()
{
    int i,j,sd=131;
    ll h;

    scanf("%d%d",&R,&C);
    for(i=1;i<=R;i++)scanf("%s",&ch[i][1]);

    for(i=1;i<=R;i++)
    {
        h=0;
        for(j=1;j<=C;j++)h=(h+ch[i][j])*sd%mod;
        Hash[i]=h;
    }

    fail[1]=j=0;
    for(i=2;i<=R;i++)
    {
        while(j>0&&Hash[j+1]!=Hash[i])j=fail[j];
        if(Hash[j+1]==Hash[i])j++;
        fail[i]=j;
    }
    rans=R-fail[R];

    for(i=1;i<=C;i++)
    {
        h=0;
        for(j=1;j<=R;j++)h=(h+ch[j][i])*sd%mod;
        Hash[i]=h;
    }

    fail[1]=j=0;
    for(i=2;i<=C;i++)
    {
        while(j>0&&Hash[j+1]!=Hash[i])j=fail[j];
        if(Hash[j+1]==Hash[i])j++;
        fail[i]=j;
    }
    cans=C-fail[C];
    printf("%d",cans*rans);
}