POJ 2185 Milking Grid 二维kmp - c++编程基础

题意：给出一个矩阵，求最小的子矩阵，使得原矩阵包含在子矩阵的某个扩展中。

比如

ABABA

就是被包含在AB扩展的矩阵中。

输出这个最小的子矩阵的大小。

其实只要两遍KMP就行了，把每行当成一个字符KMP一遍求最小循环子串的规模，然后在那几行子矩阵中把每列矩阵当成一个字符再求一遍最小循环子串。

在这里，我的做法是把矩阵求一次最小循环行后，把那几行转置后再求一次最小循环行，因为比较行直接用strcmp，很方便。

至于明明都是求行的next数组，为什么要用到两个getVal，你自己写一个就会发现原因了。

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        poj2185.cpp 
*  Create Date: 2013-11-29 08:47:14 
*  Descripton:  kmp  
*/  
  
#include   
#include   
  
const int MAXN = 10010;  
  
char T[MAXN][80], rT[80][MAXN];  
int f[MAXN];  
  
void getVal(int l) {  
    int j = -1;  
    f[0] = -1;  
    for (int i = 1; i < l; i++) {  
        while (j != -1 && strcmp(T[j + 1], T[i]))  
            j = f[j];  
        if (!strcmp(T[j + 1], T[i])) j++;  
        f[i] = j;  
    }  
}  
  
void getRevVal(int l) {  
    int j = -1;  
    f[0] = -1;  
    for (int i = 1; i < l; i++) {  
        while (j != -1 && strcmp(rT[j + 1], rT[i]))  
            j = f[j];  
        if (!strcmp(rT[j + 1], rT[i])) j++;  
        f[i] = j;  
    }  
}  
  
void rev(int r, int c) {  
    for (int i = 0; i < c; i++) {  
        for (int j = 0; j < r; j++)  
            rT[i][j] = T[j][i];  
        rT[i][r] = '\0';  
    }  
}  
  
int main() {  
    int r, c;  
    while (~scanf("%d%d", &r, &c)) {  
        for (int i = 0; i < r; i++)  
            scanf("%s", T[i]);  
        getVal(r);  
        int ans = r - f[r - 1] - 1; // the row min  
  
        rev(ans, c);    // only reverse (row min x c)  
        getRevVal(c);  
        ans = ans * (c - f[c - 1] - 1); // row min * col min  
          
        printf("%d\n", ans);  
    }  
    return 0;  
}