KMP

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/
// http://lightoj.com/volume_showproblem.php?problem=1255

#include <bits/stdc++.h>

using namespace std;

vector<int>F;

void preProcess(string s){
    F.resize(s.size()+1);

    F[0] = 0;
    F[1] = 0;

    int i = 0;
    for(int len = 2;len <= s.size();len++){
        while(i && s[len - 1] != s[i]){
            i = F[i];
        }
        if( s[len - 1] == s[i]) {
            i++;
            F[len] = i;
        } else {
            F[i] = 0;
        }
    }
}

int findMatchings(string text, string pattern) {
    int cnt = 0;

    int j = 0;
    for(int i=0;i<text.size();i++){
        while(j && text[i] != pattern[j]){
            j = F[j];
        }
        if(pattern[j] == text[i]){
            j++;
            if(j == pattern.size()){
                j = F[j];
                cnt++;
            }
        }
    }

    return cnt;
}

void init(){
    F.clear();
}

int main()
{
    int T, cas = 0;
    scanf("%d",&T);

    while(T--){
        string text;
        string pattern;

        init();
        cin>>text>>pattern;
        preProcess(pattern);
        printf("Case %d: %d\n",++cas,findMatchings(text,pattern));

    }

    return 0;
}