恩，其实大家都没有报零，反正我是蒟蒻

为了纪念我第一次打过哈希，特此写一篇题解

题目描述

从前有一个的小矩阵，矩阵的每个元素是一个字母(区分大小写)，突然有一天它发生了

变异，覆盖了整个二维空间，即不停自我复制产生相同的矩阵然后无隙放置。现在二维空间

已经被它占领了，但你只被告知了大小为R*C 空间的内容(可能包含不完整的原矩阵)，为了

将它恢复原状，你需要找到满足条件的面积最小的原矩阵。

奇怪的是，同时有 T 个二维空间发生了变异，你需要尽快解决这些变异。

输入格式

第一行为一个整数T，表示二维空间数目。

接下来T 组数据。每组数据第一行包含两个数 R，C，表示你被告知的空间大小；接下

来 R 行，每行包含 C 个字母，表示你被告知的空间内容。

输出格式

对于每一组数据输出一行，每行只包含一个数，表示最小的原矩阵面积。

样例输入

2

2 5

ABABA

ABABA

2 8

ABCDEFAB

AAAABAAA

样例输出

2

12

数据范围与约定

对于前20％的数据 R<=20，C<=20；

对于前40％的数据R<=400，C<=100；

对于100％的数据R<=5000 ，C<=100，T<=50。

前20％的数据：大暴力，枚举原矩阵的左上角和右下角，暴力判断是否满足为原矩阵。

前40％的数据：考虑到一个性质，我们一定可以将原矩阵挪到给定矩阵的左上角考虑(循环

节的性质)，那么就只用枚举原矩阵的右下角，用二维hash 可以判断两个矩形是否相等来优

化暴力，这样就能拿到40 分。

前100％的数据：

做法1：hash 暴力求出每一行可能的循环节长度，取公共的最小循环节长度即可，列同

理。将两次求得的最小循环节长度相乘即为答案。较慢，可能会超时。

做法 2：将每一行hash 为一个数，对得到的新数组直接跑KMP 求最小循环节长度，列

同理。将两次求得的最小循环节长度相乘即为答案。这就是std 做法。

一直觉得哈希是一个玄学玩意，特别怕冲突情况。但是如果哈希函数写得好，再加上人品不错，应该是可以水过去的

通常BKDRHash是比较优的

unsigned int BKDRHash(char *str)

{

    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..

    unsigned int hash = 0;

    while (*str)

    {

        hash = hash * seed + (*str++);

    }

    return (hash & 0x7FFFFFFF);

}

代码（其实就是存一个代码）

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ui unsigned int

using namespace std;

const int N=5000+5;

int r,c,nxt[N];

ui H[N];

char s[N][N];

ui hash_x(int x){

    ui seed=131;

    ui hash=0;

    for(int i=0;i<c;i++)

        hash=hash*seed+s[x][i];

    return hash;

}

ui hash_y(int x){

    ui seed=131;

    ui hash=0;

    for(int i=0;i<r;i++)

        hash=hash*seed+s[i][x];

    return hash;

}

int getkmp_x(){

    memset(nxt,0,sizeof(nxt));

    int i=0,j=-1;

    nxt[0]=-1;

    while(i<r){

        if(j==-1||H[i]==H[j]){

            i++,j++;

            nxt[i]=j;

        }

        else j=nxt[j];

    }

    return r-nxt[r];

}

int getkmp_y(){

    memset(nxt,0,sizeof(nxt));

    int i=0,j=-1;

    nxt[0]=-1;

    while(i<c){

        if(j==-1||H[i]==H[j]){

            i++,j++;

            nxt[i]=j;

        }

        else j=nxt[j];

    }

    return c-nxt[c];

}

int getans_x(){

    memset(H,0,sizeof(H));

    for(int i=0;i<r;i++)

        H[i]=hash_x(i);

    return getkmp_x();

}

int getans_y(){

    memset(H,0,sizeof(H));

    for(int i=0;i<c;i++)

        H[i]=hash_y(i);

    return getkmp_y();

}

void solve(){

    scanf("%d%d",&r,&c);

    for(int i=0;i<r;i++)

        scanf("%s",s[i]);

    int x,y;

    x=getans_x();

    y=getans_y();

    printf("%d\n",x*y);

}

int main(){

    freopen("matrix.in","r",stdin);

    freopen("matrix.out","w",stdout);

    int t;

    scanf("%d",&t);

    while(t--)

        solve();

    return 0;

}