POJ2185:Milking Grid 题解

next 数组的妙用

这道题的题意就是求能平铺成原矩阵的最小子矩阵。我们可以使用 KMP 的方法来解决这个问题。首先我们需要找出周期矩阵的横向长度，我们可以用朴素的匹配搞定这个：

for (int i = 1; i <= R; i++)
{
    scanf("%s", src[i] + 1);
    strcpy(tmp + 1, src[i] + 1);
    for (int len = C; len > 1; len--)
    {
        tmp[len] = 0;
        int x, y;
        for (x = 1, y = 1; y <= C; x++, y++)
        {
            if (!tmp[x])
                x = 1;
            if (src[i][y] != tmp[x])
                break;
        }
        if (y == C + 1)
            seg[len]++;
    }
}

其中\(src[][]\)是原始矩阵，我们在每一行中枚举\(len\)为周期长度，我们可以朴素匹配出周期，并且记录在该周期中会有多少次重复。只有重复次数为\(R\)的最短周期才能作为解之一。

之后我们快速的扫描出最短合法周期，并且把周期处设置为 0 为之后匹配提供便利。

int width = C + 1;
for (int i = 1; i <= C; i++)
    if (seg[i] == R)
    {
        width = i;
        break;
    }
for (int i = 1; i <= R; i++)
    src[i][width] = 0;

之后我们来进行求行间最小周期长度。我们可以一行一行的来进行比较，写入 next 数组。之后，我们就可以得到我们最小的周期长度了。

for (int i = 2, k = 0; i <= R; i++)
    {
        while (k && strcmp(src[i] + 1, src[k + 1] + 1))
            k = nxt[k];
        if (!strcmp(src[i] + 1, src[k + 1] + 1))
            k++;
        nxt[i] = k;
    }

最后相乘输出即可。