Substring Frequency(LOJ)

// In The Name of Almighty Allah
#include<bits/stdc++.h>
using namespace std;
#define             fastio              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define             ff                  first
#define             ss                  second
#define             int                 long long
#define             pb                  push_back
#define             pf                  push_front
#define             pii                 pair<int,int>
#define             debug(x)            cout << #x << " --->> " << x << endl;
#define             mod                 1000000009
#define             inf                 1e18
#define             clear(x)            memset(x,0,sizeof(x));
void Salman()
{
    fastio;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
int Rabin_Karp(string text, string pattern)
{
    int n = text.size(), m  = pattern.size(), cnt = 0;
    const int p = 31;

    vector<int>p_pow(m);
    p_pow[0] = 1;

    for (int i = 1; i < m; i++)
        p_pow[i] = (p_pow[i - 1] * p) % mod;

    int patt_hash = 0;
    for (int i = 0; i < m; i++)
        patt_hash = (patt_hash + (pattern[i] - 'a' + 1) * p_pow[i]) % mod;

    int curr_hash = 0;
    for (int i = 0; i < m; i++)
        curr_hash = (curr_hash + (text[i] - 'a' + 1) * p_pow[i]) % mod;
    //after calculating the hash value of first window, now slide
    for (int i = m; i < n; i++)
    {
        if (curr_hash == patt_hash) cnt++;
        curr_hash = ( ((curr_hash - (text[i - m] - 'a' + 1)) / p) + ((text[i] - 'a' + 1) * p_pow[m - 1]) ) % mod;
    }
    if (curr_hash == patt_hash) cnt++;
    return cnt;
}
main()
{
    Salman();
    int tc; cin >> tc;
    for (int i = 1; i <= tc; i++)
    {
        string text, pattern; cin >> text >> pattern;
        cout << "Case " << i << ": " << Rabin_Karp(text, pattern) << endl;
    }
}