NC13610 矩阵

题目描述

给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。

输入描述:

第一行两个整数n, m代表矩阵的长和宽；
接下来n行，每行m个字符（小写字母），表示矩阵；

输出描述:

输出一个整数表示满足条件的最大正方形的边长。

输入

5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl

输出

3

备注:

对于30%的数据，n,m≤100；
对于100%的数据，n,m≤500；

题目分析

由数据规模可推出时间复杂度应不高于。

如果暴力遍历，则时间复杂度为及以上。

考虑使用二维字符串哈希，便于快速比较两个不同的字符正方形是否相同；

同时，考虑遍历正方形边长时，使用二分查找方法。

题目代码

关于，二分查找也可以看下这篇文章，里面有些资源可以帮助理解。

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;  //使用ull可自动取模2^64

const int N = 5e2 + 10;
const int base1 = 131, base2 = 233;  //用于哈希
ull p1[N], p2[N];
map<ull, int> mp;  //统计哈希值为X的正方形个数
char s[N][N];  //原字符数组
ull h[N][N];   //哈希数组
int n, m;
//由于要求前缀和，所以下标均从1开始

bool val(int x){  //求解
    mp.clear(); //记得清除映射
    
    for(int i = x; i <= n; ++i){
        for(int j = x; j <= m; ++j){
            ull k = h[i][j] - h[i-x][j]*p2[x] - h[i][j-x]*p1[x] + h[i-x][j-x]*p2[x]*p1[x];
            ++mp[k];            
            if(mp[k] > 1) return true;
        }
    }
    
    return false;  //不满足条件
}


int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) scanf("%s", (s[i]+1));

    //1. 预处理哈希的幂次方, 用于后续字符串对齐
    p1[0] = p2[0] = 1;  //！
    for(int i = 1; i < N; ++i){
        p1[i] = p1[i-1] * base1;
        p2[i] = p2[i-1] * base2;
    }
    
    //2. 计算二维字符串前缀和
    //2.1 计算一维 行 前缀和
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            h[i][j] = h[i][j - 1] * base1 + (s[i][j]-'a');
    //2.2 计算以(i,j)为右下角的二维 矩阵 前缀和
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            h[i][j] = h[i-1][j] * base2 + h[i][j];
    
    //3. 二分法求解满足条件的正方形最大的边长
//     //此处二分法使用开区间方法 (l, r)为待查找区间
//     int l = 0, r = min(n,m)+1;
//     while(l < r-1){
//         int mid = l + (r-l)/2;
//         if(val(mid)) l = mid;
//         else r = mid;
//     } // 出来时， l == r-1
//     //[0, l]满足条件, ..., [r, min(n,m)]不满足条件
//     //l即为所求
//     cout << l << endl;
    
//     //此处二分法使用闭区间方法 [l,r]为待查找区间
//     int l = 1, r = min(n, m);
//     while(l <= r){
//         int mid = l + (r-l)/2;
//         if(val(mid)) l = mid+1;
//         else r = mid-1;
//     } //出来时，r == l-1
//     //[0, l)满足条件，...，(r, min(n,m)]不满足条件
//     //l-1即为所求
//     cout << l-1 << endl;
    
    //此处二分法使用左开右闭区间方法 [l, r)为待查找区间
    int l = 1, r = min(n,m)+1;
    while(l < r){
        int mid = l + (r-l)/2;
        if(val(mid)) l = mid+1;
        else r = mid;
    } //出来时，l == r
    //[0, l)均满足条件，...，[r, min(n,m)]均不满足条件
    //l-1即为所求
    cout << l-1 << endl;
    
    return 0;
}

三种二分查找均已通过！🎉