poj 2185(字符串Hash + KMP)

poj 2185
题意：求一个大矩阵的循环子矩阵，最后一个子矩阵可以作裁剪。
性质1：子矩阵位置在最左上方不会对答案造成影响。
性质2：行列上字母分布规律。
根据性质2，我们可以将每行 Hash，那么就只剩一行数，做一次 KMP 求最小循环节作为宽
列同理作为长
乘起来就是答案

Hash BASE 选取选大一点，13331

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, m, nxt[10005];
    char s[10005][100];
    unsigned LL BSE = 13331, hsh[10005];

    int getnxt(int len) {
        nxt[0] = nxt[1] = 0;
        for (int i = 1; i < len; ++i) {
            int j = nxt[i];
            while (j && hsh[i] != hsh[j]) j = nxt[j];
            nxt[i + 1] = (hsh[i] == hsh[j] ? j + 1 : 0);
        }
        return len - nxt[len];
    }

    void clean() {
    }
    int solve() {
        clean();
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i) scanf("%s", s[i]);
        ms(hsh, 0);
        for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) hsh[i] = hsh[i] * BSE + s[i][j];
        int ans = getnxt(n);
        ms(hsh, 0);
        for (int j = 0; j < m; ++j) for (int i = 0; i < n; ++i) hsh[j] = hsh[j] * BSE + s[i][j];
        ans *= getnxt(m);
        printf("%d\n", ans);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}