POJ2185 Milking Grid 题解 KMP算法

时间：2023-03-10 02:42:44
POJ2185 Milking Grid 题解 KMP算法

题目链接：http://poj.org/problem?id=2185

题目大意：求一个二维的字符串矩阵的最小覆盖子矩阵，即这个最小覆盖子矩阵在二维空间上不断翻倍后能覆盖原始矩阵。

题目分析：next函数的应用。需要枚举每一行每一列的字符串所对应的的 \(nxt[]\) 值，然后通过分析计算出最小的宽和最小的高。

具体分析

参考链接：https://blog.****.net/u013686535/article/details/52197467

一看这题，容易想出一种很直观的做法：求出每一行的最小重复串长度，取所有行的最小重复串长度的lcm为宽；对列也同样操作求出高。这种想法虽然很直观，但是否正确呢？

事实上，这种算法并不是正确的。如下面的这个反例：

2 8

ABCDEFAB

AAAABAAA

对于这个例子：第一行为6，第二行为5，6与5的最小公倍数为30，大于8则取8为宽，但明显是错误的。

但由于poj的测试数据太弱，以致使用这种方法的程序也可以通过。

下面介绍一下正解的做法。

首先是确定宽度：我们分别求出每行所有可能的重复子串长度，例如对于aaaa就有1、2、3和4，然后取每行都有的重复子串长度中最小的作为宽。

例如，对于上面的例子，第一行的重复子串长度只可能是6或8（显然整个串为一个重复子串也是可以的），第二行则可能是5、6、7或8，那么取它们都有的6和8当中最小值6，就是最小覆盖子矩阵的宽。

然后分成两步：

  • 考虑到每行的列数比较小， \(1 \le C \le 75\) ，可以直接暴力枚举重复子串的长度，每列逐一检查是否与当前枚举的重复子串相对应。因此求宽度这个部分的时间复杂度为 \(O(R \times C^2)\) 。
  • 找到C以后我们再来一个个枚举R就可以了，时间复杂度也是 \(O(R \times C^2)\) 。

不过我这里采用标记的方式，时间复杂度降到 \(O(R \times C)\) 。

实现代码如下：

#include <iostream>

#include <string>

#include <cstring>

#include <vector>

using namespace std;

const int maxn = 404000;

int m, nxt[maxn];

string t;

int N, M;

char ch[10010][80];

int cnt_c[80], cnt_r[10010];

void cal_next() {

    m = t.length();

    for (int i = 0, j = -1; i < m; i ++) {

        while (j != -1 && t[j+1] != t[i]) j = nxt[j];

        nxt[i] = (j+1 < i && t[j+1] == t[i]) ? ++j : -1;

    }

}

void solve() {

    // 首先清空用于记录的cnt_c和cnt_r数组

    memset(cnt_c, 0 ,sizeof(cnt_c));

    memset(cnt_r, 0, sizeof(cnt_r));

    // 遍历每一行

    for (int i = 0; i < N; i ++) {

        t = "";

        for (int j = 0; j < M; j ++) t += ch[i][j];

        cal_next();

        int j = m-1;

        while (nxt[j] != -1) {

            j = nxt[j];

            cnt_c[m-1-j] ++;

        }

    }

    // 遍历每一列

    for (int i = 0; i < M; i ++) {

        t = "";

        for (int j = 0; j < N; j ++) t += ch[j][i];

        cal_next();

        int j = m-1;

        while (nxt[j] != -1) {

            j = nxt[j];

            cnt_r[m-1-j] ++;

        }

    }

    // 找到最小的cnt_c[i]==N，没有则M

    int cc = 1, rr = 1;

    for (; cc < M; cc ++) if (cnt_c[cc] == N) break;

    // 找到最小的cnt_r[i]==M，没有则N

    for (; rr < N; rr ++) if (cnt_r[rr] == M) break;

    cout << rr * cc << endl;

}

int main() {

    while (cin >> N >> M) {

        for (int i = 0; i < N; i ++) cin >> ch[i];

        solve();

    }

    return 0;

}

作者：zifeiy

相关文章