UVA 11019 - Matrix Matcher( 2D String matching, Rolling Hash )

UVA 11019 - Matrix Matcher( 2D String matching, Rolling Hash )

Problem: Given 2D Text string and 2D pattern string, you have to

count how many times 2D pattern occurs in 2D Text.

Idea: Rolling Hash, Firstly compute hashes of segement of fixed 

window on row , then stored it.

Then, Taking these Stored hash value as alphabets calculate hash

on column on fixed window using rolling hash mechanism.

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     1002
#define inf    2000000010
#define eps    1e-9
///===============================///

ll md1=100003LL;
ll md2=101111111111LL;
ll bs1=257LL,bs2=100019LL;
ll Hs[MX+2][MX+2];
ll Hs2[MX+2][MX+2];

char s[MX+2][MX+2];
char p[MX+2][MX+2];
int x,y; /// Rolling Range;

void RollingHash2D(char s[][MX+2],int r,int c){
    ///Rolling Hash for matrix -s of size r*c.
    ///Hs[i][j] gives the hash val of length 'y' starting from row-i,col-j;

    ///At First, Row wise Y-len Hash calculation
    ll pw=1LL;/// pw for power of base
    for(int i=0;i<r;i++){
        ll h=0LL; /// h for hash value
        for(int j=0;j<y;j++){
            h=( h*bs1+s[ i ][ j ] )%md1;
            if(i==0)pw=(pw*bs1)%md1;
        }
        Hs[i][0]=h;
        for(int j=1;j<(c-y+1);j++){
            h=( h*bs1+s[ i ][ j+y-1 ] )%md1; ///Adding last char;
            h=( h-(s[ i ][ j-1 ]*pw)%md1+md1 )%md1; ///Subtracting starting char of current window;
            Hs[i][j]=h;
        }
    }

    ///Column Wise Hash calculation;
    pw=1LL;
    for(int j=0;j<(c-y+1);j++){
        ll h=0LL;
        for(int i=0;i<x;i++){
            h=( h*bs2+ Hs[i][j] )%md2;
            if(j==0)pw=(pw*bs2)%md2;
        }
        Hs2[0][j]=h;
        for(int i=1;i<(r-x+1);i++){
            h=( h*bs2+ Hs[ i+x-1 ][ j ] )%md2; ///Adding last Hash-1 val;
            h=( h-( Hs[ i-1 ][ j ]*pw )%md2+md2 )%md2; ///Removing beg Hash Val;
            Hs2[ i ][ j ]=h;
        }
    }
}

int main(){
    int tc,cs=1,i,j,k,n,m;
    S(tc);
    while(tc--){
        S2(n,m);
        for(i=0;i<n;i++){
            scanf("%s",s[i]);
        }
        S2(x,y);
        for(i=0;i<x;i++){
            scanf("%s",p[i]);
        }
        if(n<x || m<y) { /// Special case for small main matrix than pattern
            printf("0\n");
            continue;
        }
        RollingHash2D(p,x,y);
        ll vl=Hs2[0][0];
        RollingHash2D(s,n,m);
        int cnt=0;
        for(i=0;i<n-x+1;i++){
            for(j=0;j<m-y+1;j++){
                cnt+=( Hs2[i][j]==vl );
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}