I am currently solving this [problem]https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/rasta-and-kheshtak/. The main task in this problem is to find the size of maximum sub-square in two matrix. Here is the list optimizations I have done:
- First I optimized the naive matching part of finding sub-square by using hashing(A rain-karp like technique).
- Then I used binary search on the size to find the sub-square.
Can anyone suggest me bottleneck in my code?
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<fstream>
#include<string>
using namespace std;
using matrix = vector<vector<int>>;
using hmatrix = vector<vector<unsigned int>>;
struct PosHash {
int x, y;
unsigned int hash;
PosHash(int xx, int yy, unsigned int hhash): x{xx}, y{yy}, hash{hhash} {}
friend bool operator<(const PosHash& p1, const PosHash& p2);
friend bool operator==(const PosHash& p1, const PosHash& p2);
};
bool operator<(const PosHash& p1, const PosHash& p2) {
return p1.hash < p2.hash;
}
bool operator==(const PosHash& p1, const PosHash& p2) {
return p1.hash == p2.hash;
}
hmatrix buildHashMat(const matrix& m) {
hmatrix hashmat(m.size(), vector<unsigned int>(m[0].size(), 0));
for (int i = 0; i < m.size(); i++) {
for (int j = 0; j < m[0].size(); j++) {
unsigned int rowsum = (i > 0) ? hashmat[i - 1][j] : 0;
unsigned int colsum = (j > 0) ? hashmat[i][j - 1] : 0;
unsigned int psum = ((i > 0) and (j > 0)) ? hashmat[i - 1][j - 1] : 0;
hashmat[i][j] = rowsum + colsum - psum + m[i][j];
}
}
return hashmat;
}
PosHash addHash(int i, int j, int sz, const hmatrix& hashmat) {
int r1 = i + sz - 1;
int c1 = j + sz - 1;
unsigned int rowsum = (i > 0) ? hashmat[i - 1][c1] : 0;
unsigned int colsum = (j > 0) ? hashmat[r1][j - 1] : 0;
unsigned int psum = ((i > 0) and (j > 0)) ? hashmat[i - 1][j - 1] : 0;
return PosHash{ i, j, hashmat[r1][c1] - rowsum - colsum + psum };
}
bool compareMat(const matrix& m1, const matrix& m2, int x1, int y1, int x2, int y2, int sz) {
for (int i = 0; i < sz; i++) {
for (int j = 0; j < sz; j++) {
if (m1[x1 + i][y1 + j] != m2[x2 + i][y2 + j])
return false;
}
}
return true;
}
bool commonSubSquareSize(const matrix& m1, const matrix& m2, int sz, const hmatrix& hashmat1, const hmatrix& hashmat2) {
if (sz == 0) return true;
vector<PosHash> hashes;
for (int i = 0; i <= (m2.size() - sz); i++) {
for (int j = 0; j <= (m2[0].size() - sz); j++) {
hashes.push_back(addHash(i, j, sz, hashmat2));
}
}
sort(hashes.begin(), hashes.end());
for (int i = 0; i <= (m1.size() - sz); i++) {
for (int j = 0; j <= (m1[0].size() - sz); j++) {
PosHash sqhash = addHash(i, j, sz, hashmat1);
auto p = std::lower_bound(hashes.begin(), hashes.end(), sqhash);
while (p != hashes.end() and (*p) == sqhash) {
if (compareMat(m1, m2, i, j, p->x, p->y, sz))
return true;
p++;
}
}
}
return false;
}
int maxCommonSubsquare(const matrix& m1, const matrix& m2) {
int sz = min(min(min(m1.size(), m1[0].size()), m2.size()), m2[0].size());
hmatrix hashmat1 = buildHashMat(m1);
hmatrix hashmat2 = buildHashMat(m2);
int high = sz, low = 0;
while (low < high) {
int mid = (low + high + 1) / 2;
if (commonSubSquareSize(m1, m2, mid, hashmat1, hashmat2))
low = mid;
else
high = mid - 1;
}
return high;
}
matrix readMat(istream& in = std::cin) {
int m, n;
in >> m >> n;
matrix mat(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
in >> mat[i][j];
}
}
return mat;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
matrix m1 = readMat(cin);
matrix m2 = readMat(cin);
cout << maxCommonSubsquare(m1, m2);
return 0;
}