library/test/aoj/ALDS1_14_C-Pattern_Search.hash2d.test.cpp

• View this file on GitHub
• Last update: 2024-03-15 16:42:38+06:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_C

Depends on

• library/string/rollingHash2d.hpp

Code

#include <bits/stdc++.h>
using namespace std;
#include "../../string/rollingHash2d.hpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_C"

int main() {
    ios_base::sync_with_stdio(0);
    int h, w;
    cin>>h>>w;
    vector<string> s(h);
    for(int i=0;i<h;++i) {
        cin>>s[i];
    }
    int r, c;
    cin>>r>>c;
    vector<string> t(r);
    for(int i=0;i<r;++i) {
        cin>>t[i];
    }
    RollingHash2D rhs(s), rht(t);

    for(int i=0;i<h;++i) {
        for(int j=0;j<w;++j) {
            if(i+r<=h && j+c<=w) {
                if(match(rhs, i, i+r, j, j+c, rht, 0, r, 0, c)) {
                    cout<<i<<" "<<j<<'\n';
                }
            }
        }
    }
    return 0;
}

#line 1 "library/test/aoj/ALDS1_14_C-Pattern_Search.hash2d.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#line 2 "library/string/rollingHash2d.hpp"

struct RollingHash2D {
    static constexpr int M = 2;
    static constexpr long long MODS[M] = {999999937, 1000000007};
    static constexpr long long BASE_H = 9973;
    static constexpr long long BASE_W = 10007;
    vector<vector<long long>> hash[M];
    vector<long long> powH[M], powW[M];
    int h,w;
    RollingHash2D() {}
    RollingHash2D(const vector<string>& str) { init(str); }
    void init(const vector<string>& str) {
        h = str.size(), w = str[0].size();
        for(int k = 0; k < M; k++) {
            powH[k].resize(h + 1, 1);
            powW[k].resize(w + 1, 1);
            hash[k].resize(h + 1, vector<long long>(w + 1, 0));
            for(int i = 0; i < h; i++) {
                powH[k][i + 1] = powH[k][i] * BASE_H % MODS[k];
                for(int j = 0; j < w; j++) {
                    hash[k][i + 1][j + 1] = (hash[k][i + 1][j] * BASE_W % MODS[k] + str[i][j]) % MODS[k];
                }
            }
            for(int j = 0; j < w; j++) {
                powW[k][j + 1] = powW[k][j] * BASE_W % MODS[k];
                for(int i = 0; i < h; i++) {
                    hash[k][i + 1][j + 1] = (hash[k][i][j + 1] * BASE_H % MODS[k] + hash[k][i + 1][j + 1]) % MODS[k];
                }
            }
        }
    }

    // get hash [l1,r1) * [l2,r2)
    long long get(int l1, int r1, int l2, int r2, int k) {
        long long res = 0;
        res += hash[k][r1][r2];
        res -= hash[k][l1][r2] * powH[k][r1 - l1] % MODS[k];
        if(res < 0) res += MODS[k];
        res -= hash[k][r1][l2] * powW[k][r2 - l2] % MODS[k];
        if(res < 0) res += MODS[k];
        res += hash[k][l1][l2] * powH[k][r1 - l1] % MODS[k] * powW[k][r2 - l2] % MODS[k];
        if(res >= MODS[k]) res -= MODS[k];
        return res;
    }
};

bool match(RollingHash2D& RH, int L1, int R1, int L2, int R2, RollingHash2D& rh, int l1, int r1, int l2, int r2) {
    bool res = true;
    for (int k = 0; k < RollingHash2D::M; k++) {
        res &= RH.get(L1, R1, L2, R2, k) == rh.get(l1, r1, l2, r2, k);
    }
    return res;
}
#line 4 "library/test/aoj/ALDS1_14_C-Pattern_Search.hash2d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_C"

int main() {
    ios_base::sync_with_stdio(0);
    int h, w;
    cin>>h>>w;
    vector<string> s(h);
    for(int i=0;i<h;++i) {
        cin>>s[i];
    }
    int r, c;
    cin>>r>>c;
    vector<string> t(r);
    for(int i=0;i<r;++i) {
        cin>>t[i];
    }
    RollingHash2D rhs(s), rht(t);

    for(int i=0;i<h;++i) {
        for(int j=0;j<w;++j) {
            if(i+r<=h && j+c<=w) {
                if(match(rhs, i, i+r, j, j+c, rht, 0, r, 0, c)) {
                    cout<<i<<" "<<j<<'\n';
                }
            }
        }
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	6 ms	4 MB
g++	01_small_00.in	AC	6 ms	4 MB
g++	01_small_01.in	AC	6 ms	4 MB
g++	02_rand_00.in	AC	5 ms	4 MB
g++	02_rand_01.in	AC	6 ms	4 MB
g++	02_rand_02.in	AC	6 ms	4 MB
g++	02_rand_03.in	AC	6 ms	4 MB
g++	02_rand_04.in	AC	6 ms	4 MB
g++	02_rand_05.in	AC	6 ms	4 MB
g++	03_medium_00.in	AC	6 ms	4 MB
g++	03_medium_01.in	AC	7 ms	4 MB
g++	04_large_00.in	AC	81 ms	20 MB
g++	04_large_01.in	AC	80 ms	20 MB
g++	04_large_02.in	AC	81 ms	20 MB
g++	04_large_03.in	AC	76 ms	21 MB
g++	04_large_04.in	AC	76 ms	21 MB
g++	04_large_05.in	AC	69 ms	28 MB
g++	04_large_06.in	AC	78 ms	21 MB
g++	04_large_07.in	AC	75 ms	21 MB
g++	04_large_08.in	AC	74 ms	31 MB
g++	04_large_09.in	AC	76 ms	21 MB
g++	04_large_10.in	AC	113 ms	21 MB
g++	04_large_11.in	AC	110 ms	20 MB
g++	04_large_12.in	AC	109 ms	21 MB
g++	04_large_13.in	AC	111 ms	20 MB
g++	04_large_14.in	AC	66 ms	24 MB
g++	04_large_15.in	AC	80 ms	34 MB
g++	04_large_16.in	AC	89 ms	24 MB
g++	04_large_17.in	AC	87 ms	37 MB
g++	05_corner_00.in	AC	6 ms	4 MB
g++	05_corner_01.in	AC	6 ms	4 MB
g++	05_corner_02.in	AC	75 ms	31 MB
g++	05_corner_03.in	AC	80 ms	34 MB
g++	05_corner_04.in	AC	80 ms	34 MB
g++	05_corner_05.in	AC	80 ms	34 MB
g++	05_corner_06.in	AC	80 ms	34 MB

Back to top page