题目描述

求r*c矩阵中的最小覆盖子矩阵的面积。

样例

input

2 5
ABABA
ABABA

output

2

算法1

(暴力枚举) $O(极大)$

怎么暴力怎么写……

算法2

(KMP) $O(max(r,c))$

KMP求最小循环节，网上题解一抓一大把，我在此不多讨论。

算法3

(HASH) $O(rc)$

重点在此

如果你不会KMP怎么办？万能的HASH来救你！

我们先补全末尾的词：用HASH来寻找相等的两个序列，大概是这个样子：

然后再把这个序列全部复制一遍，防止出现找不到的情况。

推理得出，第一次可以将这个矩形在[r/2,+∞)中任意分割成两小块，然后只能在分出来的这一块中判断分中点可不可行，因为分出来的矩形是不能向外补全的。

然后列也是一样分割。

最后记录分出来的行、列最小值，相乘即为答案。

调了好久，部分代码直接复制粘贴，可能有点丑。

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;
char cows[40010][320];
#define ll long long
#define p1 131
#define q1 100007
#define mod 192623317
unsigned int p1c[40010];
unsigned int q1c[320];
unsigned int hash1[40010][320];//本来写了双HASH的，结果MLE了，就删了一个
unsigned int gethash1(int x1,int y1,int x2,int y2){
    return (((ll)hash1[x2][y2]-(ll)hash1[x1][y2]*p1c[x2-x1]%mod-(ll)hash1[x2][y1]*q1c[y2-y1]%mod+(ll)hash1[x1][y1]*p1c[x2-x1]%mod*q1c[y2-y1]%mod)+mod)%mod;
}//获得[x1+1,y1+1]~[x2,y2]的HASH值
int r,c;
int h,l;
void workh(int r){//在分出来的小矩形中判断中点可不可行
    h=min(h,r);
    if(r&1) return;//奇数行肯定不行
    if(gethash1(0,0,r/2,c)==gethash1(r/2,0,r,c)) workh(r/2);
}
void workl(int r){//同上
    l=min(l,r);
    if(r&1) return;
    if(gethash1(0,0,h,r/2)==gethash1(0,r/2,h,r)) workl(r/2);
}
int main(){
    cin>>r>>c;
    int bfr=r,bfc=c;
    for(int i=1;i<=r;i++)
        scanf("%s",cows[i]+1);
    p1c[0]=q1c[0]=1;
    for(int i=1;i<=r;i++){
        p1c[i]=(ll)p1c[i-1]*p1%mod;
    }
    for(int i=1;i<=c;i++){
        q1c[i]=(ll)q1c[i-1]*q1%mod;
    }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){
            hash1[i][j]=(((ll)hash1[i-1][j]*p1%mod+(ll)hash1[i][j-1]*q1%mod-(ll)hash1[i-1][j-1]*p1%mod*q1%mod+cows[i][j])%mod+mod)%mod;
        }//预处理
    l=-1;
    for(int j=c/2;j>=1;j--)
        if(gethash1(0,0,r,j)==gethash1(0,c-j,r,c)){//判断最长匹配长度
            l=j;
            break;
        }
    if(l!=-1){//然后补全末尾单词
        for(int i=1;i<=r;i++)
            for(int j=l+1;j<=c-l;j++)
                cows[i][j+c-l]=cows[i][j];
        for(int i=1;i<=r;i++)
            for(int j=c+1;j<=(c-l)*2;j++){
                hash1[i][j]=(((ll)hash1[i-1][j]*p1%mod+(ll)hash1[i][j-1]*q1%mod-(ll)hash1[i-1][j-1]*p1%mod*q1%mod+cows[i][j])%mod+mod)%mod;
            }
        for(int i=c+1;i<=(c-l)*2;i++){
            q1c[i]=(ll)q1c[i-1]*q1%mod;
        }//更新HASH
        c=(c-l)*2;
    }

    l=-1;
    for(int j=r/2;j>=1;j--)//同上
        if(gethash1(0,0,j,c)==gethash1(r-j,0,r,c)){
            l=j;
            break;
        }
    if(l!=-1){
        for(int j=1;j<=c;j++)
            for(int i=l+1;i<=r-l;i++)
                cows[i+r-l][j]=cows[i][j];
        for(int i=r+1;i<=(r-l)*2;i++)
            for(int j=1;j<=c;j++){
                hash1[i][j]=(((ll)hash1[i-1][j]*p1%mod+(ll)hash1[i][j-1]*q1%mod-(ll)hash1[i-1][j-1]*p1%mod*q1%mod+cows[i][j])%mod+mod)%mod;
            }
        for(int i=r+1;i<=(r-l)*2;i++){
            p1c[i]=(ll)p1c[i-1]*p1%mod;
        }
        r=(r-l)*2;
    }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cows[i][j+c]=cows[i+r][j]=cows[i+r][j+c]=cows[i][j];//再向外复制一份，保证递归时最后能找到最优解
    for(int i=1;i<=r+r;i++)
        for(int j=1;j<=c+c;j++)
            if(i>r||j>c){
                hash1[i][j]=(((ll)hash1[i-1][j]*p1%mod+(ll)hash1[i][j-1]*q1%mod-(ll)hash1[i-1][j-1]*p1%mod*q1%mod+cows[i][j])%mod+mod)%mod;
            }//继续更新HASH值
    r+=r;c+=c;
    h=bfr;l=bfc;
    if(r!=1)
    for(int i=bfr/2+((bfr/2)&1);i<=r/2;i++)//判断分出来的两个矩阵是否相等
    //矩阵：[1,1]   [1,c]
    //      [i,1]   [i,c]
    //和：  [i+1,1] [i+1,c]
    //      [i*2,1] [i*2,c]
        if(gethash1(0,0,i,c)==gethash1(i,0,i*2,c))
            workh(i);
    if(c!=1)
    for(int i=bfc/2+((bfc/2)&1);i<=c/2;i++)//同上
        if(gethash1(0,0,h,i)==gethash1(0,i,h,i*2))
            workl(i);
    printf("%d",h*l);
    return 0;
}