// count prefix occurrence
    static int countOccurrences(String str, String pattern){
        int count = 0;
        if(str == null || pattern == null)
            return 0;
        else if(str.length() == 0 || pattern.length() == 0)
            return 0;
        else {
            int start = 0;
            int k = 0;
            int len = pattern.length();
            int i = 0;
            while(i < str.length()){
                if(str.charAt(i) == pattern.charAt(k)){
                    if(k == 0)
                        start = i;
                    k++;
                    if(k == len){
                        count++;
                        k = 0;
                        i = start + 1;
                    }else{
                        i++;
                    }
                }else{
                    k = 0;
                    i = start + 1;
                    start++;
                }
            }
        }
        return count;
    }

// str: aaa 
// pat: aa
int count_occurrences(string str, string pat){
    int len = pat.length();
    int k = 0;
    int start = 0;
    int i = 0;
    int count = 0;
    while(i < str.length()){
        if(str[i] == pat[k]){
            if(k == 0)
                start = i;
            k++;
            if(k == len){
                count++;
                k = 0;

                start++;
                i = start;
            }else{
                i++;
            }
        }else{
            // reset start
            start++;
            i = start;
        }

    }
    return count;
}