Hashing

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define MAX 1200005

const ll base = 341;
const ll mod = 1000000007;

ll po[MAX], inv[MAX];

ll bigMod(ll a, ll x)
{
    if(x == 0LL) return 1LL;
    if(x == 1LL) return a;
    ll ret = bigMod(a, x/2);
    ret = (ret*ret)%mod;
    if(x & 1LL) ret = (ret*a)%mod;
    return ret;
}

void gen()
{
    po[0] = 1;
    for(int i=1; i<MAX; i++) po[i] = (po[i-1]*base)%mod;
    inv[MAX-1] = bigMod(po[MAX-1], mod-2);
    for(int i=MAX-2; i>=0; i--) inv[i] = (inv[i+1]*base)%mod;
}

void genPrefixHash(string &str, vector<ll> &v)
{
    int n = (int) str.length();
    ll sum = 0;
    v.push_back(sum);
    for(int i=0; i<n; i++){
        sum += ((str[i]-'a')*po[i+1])%mod;
        if(sum > mod) sum -= mod;
        v.push_back(sum);
    }
}

ll substringHash(vector<ll> &prefixHash, int l, int r)
{
    ll sum = prefixHash[r]-prefixHash[l-1];
    if(sum < 0) sum += mod;
    sum = (sum*inv[l-1])%mod;
    return sum;
}

string text, pattern;
vector<ll> textHash, patternHash;

void clr()
{
    text.clear();
    pattern.clear();
    textHash.clear();
    patternHash.clear();
}

int matched(int st, int l)
{
    int m = (int) pattern.length();
    int best = l-1;
    int low = l, high = st+m-1;
    while(low <= high){
        int mid = (low+high)/2;
        ll textValue = substringHash(textHash, l, mid);
        ll patternValue = substringHash(patternHash, l-st+1, mid-st+1);
        if(textValue == patternValue){
            best = mid;
            low = mid+1;
        }
        else {
            high = mid-1;
        }
    }
    return best;
}

bool calc(int st, int ed, int cur, int rem)
{
    if(rem < 0) return false;
    cur = matched(st, cur+1);
    if(rem != 0) cur++;
    if(cur >= ed) return true;
    return calc(st, ed, cur, rem-1);
}

int main()
{
    //freopen("in.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    gen();
    int cases;
    cin >> cases;
    int caseno = 0;
    while(cases--){
        clr();
        cin >> text >> pattern;
        int k;
        cin >> k;
        genPrefixHash(text, textHash);
        genPrefixHash(pattern, patternHash);
        int n = (int) text.length();
        int m = (int) pattern.length();
        int ans = 0;
        for(int i=1; i<=n-m+1; i++){
            ll val1 = substringHash(textHash, i, i+m-1);
            ll val2 = substringHash(patternHash, 1, m);
        }
        for(int i=1; i<=n-m+1; i++){
            if(calc(i, i+m-1, i-1, k)){
                ans++;
            }
        }
        cout << "Case " << ++caseno << ": " << ans << endl;
    }
}